Coding > FPC Valkyrie

Suggested "vnode" expansion

(1/3) > >>

Igor Savin:
I've been using modified vnode for a while; in order to preserve compatibility with ever-changing Valkyrie I'm asking for the following changes:

3 new functions, 1 new procedure and one tweak.

TNode.


--- Code: ---       function LastChild : TNode; {OK, I know there is Child.prev, but I prefer writing code in plain English}
       function ReturnExactChild (const Position : Word) : TNode;
       function ReturnRandomChild : TNode; //uses ChildCount variable which is described later
       procedure DestroyAllChild; //destroy all children but keep parent intact

--- End code ---

1:


--- Code: ---function TNode.LastChild : TNode;
begin
if hasChild then exit (Child.prev) else exit (nil);
end;
--- End code ---


2:


--- Code: ---function TNode.ReturnExactChild (const Position : Word) : TNode;

var i : Byte;
      RC : TNode;

begin

RC:=Child;

if Position>1 then for i:=1 to Position-1 do RC:=RC.Next;

exit (RC);
end;
--- End code ---



3:


--- Code: ---function TNode.ReturnRandomChild : TNode;
begin

if hasChild then Exit (ReturnExactChild (Random(ChildCount)+1))
else Exit (nil);

end;

--- End code ---

4:


--- Code: ---procedure TNode.DestroyAllChildren;
begin
while Child <> nil do Child.Destroy;
end;

--- End code ---
\\\

TNode tweak:

additional field
       ChildCount : Word; {How many Children this Node has; I use it very often}

***

TNode.Create
+ChildCount := 0; //in the end of constructor

***

TNode.Add
+inc (ChildCount); //in the end of procedure

TNode.Detach
  if Parent <> nil then begin //in the beginning
    dec (Parent.ChildCount);


p. s. If you accept any of the mentioned changes, I can supply modified "vnode.pas", although modification needed, as you can see, is rather modest.

Kornel Kisielewicz:
Most of those seem reasonable so I could add them, but I have a couple questions/comments :


* where do you need LastChild?
* ReturnExact child -- this is bad, because in terms of programming terms, Nodes' children are equal -- so a child has no "index". Moreover it gives the temptation to loop through the children like an array -- what is also wrong, because it is very inefficient. A good and proper solution might be to create a "TArrayNode" which additionaly holds it's children in an array.
* Return Random child also suffers from the above -- also it's a equally weighted pick, which in most cases is useless. In my case I use TWeightedList for these.
* DestroyAllChildren -- what would you need that for?
* Curiosity -- why do you use the number of nodes so often?
Also, remember that you can just inherit TNode, and extend it with all the functionality listed above WITHOUT touching TNode :)

First two points here actually brought me to the topic that I was most concerned about when implementing TNode -- there is no "straightforward" way to loop through the children of a node when they are double linked. This is the current official and optimized way:


--- Code: (Delphi) ---var Scan : TNode;
begin
  Scan := Child;
  if Scan <> nil then
  repeat
    ... // do stuff with Scan
    Scan := Scan.Next;
  until Scan = Child;
end; 

--- End code ---

However this is not nice. I thought about implementing something alike C++ iterators, unfortunately we don't have any control over step in FreePascal, nor over the loop variable :/. I have to think about it more.

However:


--- Code: (Delphi) ---var i : Word;
begin
  for i := 1 to ChildCount do
     with ReturnExactChild(i) do
        ...
end; 

--- End code ---

Is definitively not the way to go.

Igor Savin:
\where do you need LastChild?\

For an example, if I have just created a new object inside a list (Party.Add (TCreature.Init)) and want to do something with it, that goes beyond the scope of default creature initialization\set up.

\Return Random child also suffers from the above -- also it's a equally weighted pick, which in most cases is useless\

Example use: I have a list of unassigned Warlords; when a new army emerges, random Warlord gets chosen from the list. Or display randomly chosen rumour from a pack.

\DestroyAllChildren -- what would you need that for?\

Example use: Global Loot list, which is filled with dead creature's posessions, called by Looter, who takes whatever he wants from it, then purged; there's no reason to FreeAndNil and then re-Create it, as it's used all the time.

\remember that you can just inherit TNode, and extend it with all the functionality listed above WITHOUT touching TNode :)\

...even though I use inheritance heavily, that one somehow missed me. My bad.

Lots of overrides would be needed to include working ChildCount, though, so that one would preferably be included anyway.


\Curiosity -- why do you use the number of nodes so often?\

It's very convenient. This way I need not to manually monitor how many Heroes are in party (for them not to exceed Leadership-allowed limit), how many items in a pack etc.


\\\

\...Is definitively not the way to go.\

Hey, I'm not THAT pathetic! I use "official and optimized" way for iterations; ExactChild has some other uses, like returning requested Event from a EventList (which has constant position, as only new events are added with time). And it's faster than manual

repeat
...
until Node.ID=RequestedID

since no checks are performed. Of course using arrays is a fine method just as well, but it requires additional coding...

It is not used frequently and I can get rid of it completely if necessary; mostly it's called from ReturnRandomChild, which is used more commonly; thus those two can be merged.


I'll check TArrayNode and TWeightedList; never tried those.


p. s. Why are you using conversion between pointers and ordinals in vini.pas so widely? It doesn't compile under Linux.

Kornel Kisielewicz:

--- Quote from: Igor Savin on January 14, 2008, 09:23 ---\where do you need LastChild?\

For an example, if I have just created a new object inside a list (Party.Add (TCreature.Init)) and want to do something with it, that goes beyond the scope of default creature initialization\set up.

--- End quote ---
Oh no, never do that. Because you don't know wheter creation was successful -- TCreature.Create (you should use Create for all constructors -_-) can return nil if out of memory, or a error happens. So if you access last child then you might access the wrong child, and finding that bug would be almost impossible!

BTW, Party can override Add, and keep last creature added as a TCreature pointer -- this way you'll be able to avoid typecasts too, and be a lot safer!


--- Quote from: Igor Savin on January 14, 2008, 09:23 ---\Return Random child also suffers from the above -- also it's a equally weighted pick, which in most cases is useless\

Example use: I have a list of unassigned Warlords; when a new army emerges, random Warlord gets chosen from the list. Or display randomly chosen rumour from a pack.

--- End quote ---
Hmm maybe -- I don't create nodes of non-existing beings however. A TManagedArray would be a wiser choice here anyway.


--- Quote from: Igor Savin on January 14, 2008, 09:23 ---\remember that you can just inherit TNode, and extend it with all the functionality listed above WITHOUT touching TNode :)\

...even though I use inheritance heavily, that one somehow missed me. My bad.

Lots of overrides would be needed to include working ChildCount, though, so that one would preferably be included anyway.

--- End quote ---

Yeah, child count will probably make it in.


--- Quote from: Igor Savin on January 14, 2008, 09:23 ---\...Is definitively not the way to go.\

Hey, I'm not THAT pathetic! I use "official and optimized" way for iterations; ExactChild has some other uses, like returning requested Event from a EventList (which has constant position, as only new events are added with time). And it's faster than manual

repeat
...
until Node.ID=RequestedID

since no checks are performed. Of course using arrays is a fine method just as well, but it requires additional coding...

It is not used frequently and I can get rid of it completely if necessary; mostly it's called from ReturnRandomChild, which is used more commonly; thus those two can be merged.

--- End quote ---

However it's a linear search, which is SLOW. Arrays are direct, so there's no search time.


--- Quote from: Igor Savin on January 14, 2008, 09:23 ---I'll check TArrayNode and TWeightedList; never tried those.

--- End quote ---
The first one doesn't exist yet, but I'll implement it, for it may come in use soon!


--- Quote from: Igor Savin on January 14, 2008, 09:23 ---p. s. Why are you using conversion between pointers and ordinals in vini.pas so widely? It doesn't compile under Linux.

--- End quote ---
It does under 32bit linux, or else there'd be no DoomRL for linux :P. The vini.pas is very outdated -- I'll rewrite it soon (probably using the new vds.pas and/or variant arrays).

Kornel Kisielewicz:
ChildCount and DestroyChildren implemented in revision 108.

Navigation

[0] Message Index

[#] Next page

Go to full version