Chaosforge Forum

  • November 03, 2024, 17:55
  • Welcome, Guest
Please login or register.



Login with username, password and session length
Pages: [1]

Author Topic: Suggested "vnode" expansion  (Read 13985 times)

Igor Savin

  • Elder Chaos Guard
  • Second Lieutenant
  • *
  • *
  • Offline Offline
  • Posts: 180
    • View Profile
Suggested "vnode" expansion
« on: January 12, 2008, 08:23 »

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: [Select]
       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

1:

Code: [Select]
function TNode.LastChild : TNode;
begin
if hasChild then exit (Child.prev) else exit (nil);
end;


2:

Code: [Select]
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;



3:

Code: [Select]
function TNode.ReturnRandomChild : TNode;
begin

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

end;

4:

Code: [Select]
procedure TNode.DestroyAllChildren;
begin
while Child <> nil do Child.Destroy;
end;
\\\

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.
« Last Edit: January 12, 2008, 08:29 by Igor Savin »
Logged

Kornel Kisielewicz

  • God Hand
  • Apostle
  • *
  • *
  • Offline Offline
  • Posts: 4576
    • View Profile
    • http://chaosforge.org/
Re: Suggested "vnode" expansion
« Reply #1 on: January 12, 2008, 19:51 »

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) [Select]
var Scan : TNode;
begin
  Scan := Child;
  if Scan <> nil then
  repeat
    ... // do stuff with Scan
    Scan := Scan.Next;
  until Scan = Child;
end; 

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) [Select]
var i : Word;
begin
  for i := 1 to ChildCount do
     with ReturnExactChild(i) do
        ...
end; 

Is definitively not the way to go.
Logged
at your service,
Kornel Kisielewicz

Igor Savin

  • Elder Chaos Guard
  • Second Lieutenant
  • *
  • *
  • Offline Offline
  • Posts: 180
    • View Profile
Re: Suggested "vnode" expansion
« Reply #2 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.

\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.
Logged

Kornel Kisielewicz

  • God Hand
  • Apostle
  • *
  • *
  • Offline Offline
  • Posts: 4576
    • View Profile
    • http://chaosforge.org/
Re: Suggested "vnode" expansion
« Reply #3 on: January 14, 2008, 13:14 »

\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.
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!

\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.
Hmm maybe -- I don't create nodes of non-existing beings however. A TManagedArray would be a wiser choice here anyway.

\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.

Yeah, child count will probably make it in.

\...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.

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

I'll check TArrayNode and TWeightedList; never tried those.
The first one doesn't exist yet, but I'll implement it, for it may come in use soon!

p. s. Why are you using conversion between pointers and ordinals in vini.pas so widely? It doesn't compile under Linux.
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).
Logged
at your service,
Kornel Kisielewicz

Kornel Kisielewicz

  • God Hand
  • Apostle
  • *
  • *
  • Offline Offline
  • Posts: 4576
    • View Profile
    • http://chaosforge.org/
Re: Suggested "vnode" expansion
« Reply #4 on: January 14, 2008, 13:32 »

ChildCount and DestroyChildren implemented in revision 108.
Logged
at your service,
Kornel Kisielewicz

Igor Savin

  • Elder Chaos Guard
  • Second Lieutenant
  • *
  • *
  • Offline Offline
  • Posts: 180
    • View Profile
Re: Suggested "vnode" expansion
« Reply #5 on: January 14, 2008, 13:52 »

\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\

Point taken.

\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!\

Hmmm... This requires additional coding just as well, but might be great structure-wise. Thanks.

\A TManagedArray would be a wiser choice here anyway\

I'll look into it.

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

Project Sa...?..

\It does under 32bit linux, or else there'd be no DoomRL for linux :P.\

Ah, so it's my x64 to be blamed :).

\ChildCount and DestroyChildren implemented in revision 108\

Splendid.

A question: Why not call TNode.Clean from TNode.Create? What's the rationale behind redundant code?
Logged

Kornel Kisielewicz

  • God Hand
  • Apostle
  • *
  • *
  • Offline Offline
  • Posts: 4576
    • View Profile
    • http://chaosforge.org/
Re: Suggested "vnode" expansion
« Reply #6 on: January 14, 2008, 13:58 »

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

Project Sa...?..
Yep. It will take advantage of all Valkyrie features like EventQueues and UIDs, and of yet unimplemented features as well (Messages ^^).

\It does under 32bit linux, or else there'd be no DoomRL for linux :P.\

Ah, so it's my x64 to be blamed :).
No, my laziness is to be blamed xP.

\ChildCount and DestroyChildren implemented in revision 108\

Splendid.

A question: Why not call TNode.Clean from TNode.Create? What's the rationale behind redundant code?
Point taken, revision 109 commited.
Logged
at your service,
Kornel Kisielewicz

Igor Savin

  • Elder Chaos Guard
  • Second Lieutenant
  • *
  • *
  • Offline Offline
  • Posts: 180
    • View Profile
Re: Suggested "vnode" expansion
« Reply #7 on: January 15, 2008, 09:34 »

Kornel, there is a potential problem in current ChildCount mechanism. Since Detach (which decreases the counter) does not set Parent to nil, if I first manually Detach node and then Add it somewhere, counter will be decreased twice (parent<> nil -> Detach).

It might be a better idea to couple dec(ChildCount) with Destroy and Add.

Or finally make Detach set Parent to nil :). Do you actually ever need Parent of detached node?..
Logged

Kornel Kisielewicz

  • God Hand
  • Apostle
  • *
  • *
  • Offline Offline
  • Posts: 4576
    • View Profile
    • http://chaosforge.org/
Re: Suggested "vnode" expansion
« Reply #8 on: January 15, 2008, 09:43 »

Parent should be set to nil anyway. I hope that doesn't produce errors in existing code. I'll commit that change.
Logged
at your service,
Kornel Kisielewicz

Igor Savin

  • Elder Chaos Guard
  • Second Lieutenant
  • *
  • *
  • Offline Offline
  • Posts: 180
    • View Profile
Re: Suggested "vnode" expansion
« Reply #9 on: January 15, 2008, 10:06 »

Thanks for all the support provided; I hope I won't bug you anymore in the nearest future. Sorry for all the inconvenience caused; I understand you have your own battles to fight (and latest DoomRL release doesn't seem to go so smoothly). I really appreciate your kind attention.
Logged

Kornel Kisielewicz

  • God Hand
  • Apostle
  • *
  • *
  • Offline Offline
  • Posts: 4576
    • View Profile
    • http://chaosforge.org/
Re: Suggested "vnode" expansion
« Reply #10 on: January 15, 2008, 10:31 »

Nah, improoving Valkyrie is what counts -- the more comments and suggestions the better all chaosforge games will become :D
Logged
at your service,
Kornel Kisielewicz
Pages: [1]