How to handle unlimited nested repeating conditions?

Author

Message

Latch

19

Years of Service

User Offline

Joined: 23rd Jul 2006

Location:

Posted: 9th Jun 2007 02:42

Link

I'm looking for a way to handle conditions that may repeat over and over and be nested inside each other. An example would be a 3d hierarchy where you can have bone after bone or mesh after mesh related to one another in a parent child relationship.

The goal is to be able to read back this "tree" without having to go through a set number of iterations for whatever depth of nesting there could be. I don't always want to have to dig down 100s of tiers to try and catch all the possibilities. Let's say there are two cases that the condition could be. And for each of these cases, the same two cases could be under them. Here's a pseudo code example:

+ Code Snippet

for n = start to finish
   if case1 = true

      if case1=true

         if case1=true
            etc.
         if case2=true

      endif

      if case2=true

         if case1=true
            etc
         if case2=true

      endif

   endif

   if case2 = true
      etc

next n

A human skeleton, for example, could have a hierarchy that starts with the spine > hips > thigh > leg > ankle > foot > toe base > toe middle > toe tip etc.

This example is 10 cases deep and if each case along the way could have other branches, how do I program to adjust for various depths instead of setting a maximum depth that I would look down the tree each time?

Enjoy your day.

Back to top

Profile PM

waffle

23

Years of Service

User Offline

Joined: 9th Sep 2002

Location: Western USA

Posted: 9th Jun 2007 08:53

Link

the simple answer is you can't.

What you generally do is called recursion ....
Have a function call itself

+ Code Snippet

example:
for this example, I will assume you are reading a file
function SearchNode(count,start)
`count is to determine maxe depth
`start is the line in the file to read
if count > 99999 then exitfunction
set file pointer to start line
do
read data from file
start=start+1
if this is a new node then SearchNode(count + 1, start)
loop
endfunction

that should be enough to get the idea.
In C++, each time a function is called, the function
gets a new stack space with new variables ....
In DBC, all variables are STATIC.
But, as long as you know this, this will work fine.

If you are wondering how to easily jump around a file,
Try first loading the entire file into a global variable ...
I use Dim FileLine$(MaxLines) to store file data.
And then just load the file into the Dim before actually
checking out the data.

A minor problem for you will be determine how to store your data.
One methode would be to first scan the file to determine how many
Nodes there are and then

+ Code Snippet

Dim Nodes(Total,DataCount)
dim Parent(Total)
where total is the total number of Nodes
DataCount is the maximum number of childs than any node can have
Parent indentifies the parent of the Node

Back to top

Profile PM Email Website

Latch

19

Years of Service

User Offline

Joined: 23rd Jul 2006

Location:

Posted: 9th Jun 2007 18:33 Edited at: 10th Jun 2007 17:25

Link

Thanks Waffle, that makes sense.

[EDIT]

I'll try setting up a recursive function.

Enjoy your day.

Back to top

Profile PM

Libervurto

20

Years of Service

User Offline

Joined: 30th Jun 2006

Location: On Toast

Posted: 30th Jun 2007 22:07

Link

Damn you waffle!

I was gonna sound clever suggesting a recursive function.
Could you please explain what you mean by

Quote: "
In C++, each time a function is called, the function
gets a new stack space with new variables ....
In DBC, all variables are STATIC.
But, as long as you know this, this will work fine.
"

@ latch
Here is the only program I've made with good recursive functions, it should help you understand how to use them. If you already understand them have a look anyway, it's cool lol.

`*** The Towers of Hanoi Problem ***
`I will use binary system to store rings on poles (1=small ring, 2=medium, 4=large)
DIM Pole(3)
source = 1 : `set start pole
`setup
hide mouse
sync on

DO
`set up new puzzle
repeat : destination= rnd(2)+1 : until destination <> source : `get end pole
repeat : temporary_store= rnd(2)+1 : until temporary_store <> source and temporary_store <> destination
Pole(source) = 7 : Pole(destination) = 0 : Pole(temporary_store) = 0 : `initiate poles
display() : `display the initial puzzle
print "New destination: " ; destination : sync : wait 1000 : `begin puzzle message
source = Transfer(3, source, destination, temporary_store) : `complete the puzzle and return new source
LOOP

`Transfer
FUNCTION Transfer(N, source, destination, temporary_store)
   `Problem Fix Variables
   S = source
   D = destination
   T = temporary_store

If N = 1
      Move(S, D)
   Else
      Transfer(N-1, S, T, D)
      Move(S, D)
      Transfer(N-1, T, D, S)
   Endif
ENDFUNCTION destination

`Move
FUNCTION Move(source, destination)
   `which ring is to be moved?
   Select Pole(source)
      Case 1 : ring = 1 : Endcase
      Case 2 : ring = 2 : Endcase
      Case 3 : ring = 1 : Endcase
      Case 4 : ring = 4 : Endcase
      Case 5 : ring = 1 : Endcase
      Case 6 : ring = 2 : Endcase
      Case 7 : ring = 1 : Endcase
   Endselect
   `Take ring from source and add to destination
   Pole(source) = Pole(source) - ring
   Pole(destination) = Pole(destination) + ring
   `Update display
   Display()
ENDFUNCTION

`Display
FUNCTION Display()
cls
For x = 1 to 3
   `draw poles
   ink rgb(120,40,0),0
   Line 100+(100*x), 100, 100+(100*x), 200
   `disintegrate pole variables
   ink rgb(255,200,0),0
   pole = Pole(x) : `store current pole rings value
   rings = 0
      `big ring?
      if pole - 4 >=0
         inc rings
         box 100+(100*x)-40, 183-((rings-1)*20), 100+(100*x)+40, 200-((rings-1)*20)
         pole = pole - 4
      endif
      `medium ring?
      if pole - 2 >=0
         inc rings
         box 100+(100*x)-30, 183-((rings-1)*20), 100+(100*x)+30, 200-((rings-1)*20)
         pole = pole - 2
      endif
      `small ring?
      if pole - 1 >=0
         inc rings
         box 100+(100*x)-20, 183-((rings-1)*20), 100+(100*x)+20, 200-((rings-1)*20)
         pole = pole - 1
      endif
Next x
sync
wait 1000
ENDFUNCTION

+ Code Snippet

`*** The Towers of Hanoi Problem ***
`I will use binary system to store rings on poles (1=small ring, 2=medium, 4=large)
DIM Pole(3)
source = 1 : `set start pole
`setup
hide mouse
sync on

DO
`set up new puzzle
repeat : destination= rnd(2)+1 : until destination <> source : `get end pole
repeat : temporary_store= rnd(2)+1 : until temporary_store <> source and temporary_store <> destination
Pole(source) = 7 : Pole(destination) = 0 : Pole(temporary_store) = 0 : `initiate poles
display() : `display the initial puzzle
print "New destination: " ; destination : sync : wait 1000 : `begin puzzle message
source = Transfer(3, source, destination, temporary_store) : `complete the puzzle and return new source
LOOP

`Transfer
FUNCTION Transfer(N, source, destination, temporary_store)
   `Problem Fix Variables
   S = source
   D = destination
   T = temporary_store

   If N = 1
      Move(S, D)
   Else
      Transfer(N-1, S, T, D)
      Move(S, D)
      Transfer(N-1, T, D, S)
   Endif
ENDFUNCTION destination

`Move
FUNCTION Move(source, destination)
   `which ring is to be moved?
   Select Pole(source)
      Case 1 : ring = 1 : Endcase
      Case 2 : ring = 2 : Endcase
      Case 3 : ring = 1 : Endcase
      Case 4 : ring = 4 : Endcase
      Case 5 : ring = 1 : Endcase
      Case 6 : ring = 2 : Endcase
      Case 7 : ring = 1 : Endcase
   Endselect
   `Take ring from source and add to destination
   Pole(source) = Pole(source) - ring
   Pole(destination) = Pole(destination) + ring
   `Update display
   Display()
ENDFUNCTION

`Display
FUNCTION Display()
cls
For x = 1 to 3
   `draw poles
   ink rgb(120,40,0),0
   Line 100+(100*x), 100, 100+(100*x), 200
   `disintegrate pole variables
   ink rgb(255,200,0),0
   pole = Pole(x) : `store current pole rings value
   rings = 0
      `big ring?
      if pole - 4 >=0
         inc rings
         box 100+(100*x)-40, 183-((rings-1)*20), 100+(100*x)+40, 200-((rings-1)*20)
         pole = pole - 4
      endif
      `medium ring?
      if pole - 2 >=0
         inc rings
         box 100+(100*x)-30, 183-((rings-1)*20), 100+(100*x)+30, 200-((rings-1)*20)
         pole = pole - 2
      endif
      `small ring?
      if pole - 1 >=0
         inc rings
         box 100+(100*x)-20, 183-((rings-1)*20), 100+(100*x)+20, 200-((rings-1)*20)
         pole = pole - 1
      endif
Next x
sync
wait 1000
ENDFUNCTION

I make music and art. Here is a sample of my art: done in Paint! It's all I have

Back to top

Profile PM Email

Latch

19

Years of Service

User Offline

Joined: 23rd Jul 2006

Location:

Posted: 1st Jul 2007 01:49

Link

@Obese

Thanks for the example.

I ended up taking another approach with my program as the stack kept getting out of control - there was a limit as to how deep the recursion could go and I don't think I was managing it properly. I ended up calling the function from an outside loop and just passing the loop counter as a global and under certain conditions forcing my way out of the function and updating or decrementing the main loop counter. The info from the function was stored in an array in sequential order in a manner that fit the "tree" I wanted to build.

Enjoy your day.

Back to top

Profile PM

Libervurto

20

Years of Service

User Offline

Joined: 30th Jun 2006

Location: On Toast

Posted: 1st Jul 2007 13:12

Link

Is this for the DBC challenge?
I was thinking of doing something like that for storing word relationships e.g.

+ Code Snippet

Noun
 ^ Place
    ^ France
       ^ Paris

Verb
 ^ Run

I make music and art. Here is a sample of my art: done in Paint! It's all I have

Back to top

Profile PM Email

Sorry your browser is not supported!

DarkBASIC Discussion / How to handle unlimited nested repeating conditions?