Recursion help

[TokenHerbz]

I'm trying to make a CODE that will beable to find its way from start to finish by going only on the tiles with access, (not out of bounds/blocks)

So the concept would be to keep calling the same function over untill it reaches the end, however i I request something ontop of just that.

1) After this finds the path from start to finish, it must REMEMBER the path so it doesn't have to check the path again, say if i want to redo the maze/path again.
How would I best go about doing that? I've sat and thought about different ways however all don't seem to be that logical to implement into my code to use.

**Notes**, Not that i think it would matter to much, but "Each" tile on the map is an object, And so are the "things" That must find its way threw the tiles.

Its a 2D tile set up, and everything is an object in the code. (YAY FOR CLASSES)


Any tips with math regarding quicker recursion or some ideas to how i could store the final "solved path" so that i don't have to "redo the solving" each time, would be phanominal.

Thanks a ton guys! If you need code let me know, i'll post it.

[Brightguy]

Are you familiar with, say, depth-first search? That has an easy recursive implementation. Once the finish tile is found, you can stop recursing and output the path (in reverse order) from start to finish. (Actually, you can avoid the recursion overhead by just storing the tiles being searched in a stack.)

[A.J]

Like Brightguy mentioned, you have to backtrack your way from the end to the beginning. Think of it as laying crumbles of bread on the way to the finish, and merely walking back. One way to do this is to store the 'parent' tile of each tile (i.e. the tile that was visited before the current tile).

[TokenHerbz]

okay, I'm still not able to achieve my end goal here.

What I am able to achieve:
1) To solve the PATH
2) Able to DRAW over the PATH to prove it
3) Able to "memorize" path (so i think)

What I am unable to achieve:
1) to "draw" a line threw the path 1 PIXEL THICK, threw the middle of each tile regardless of directions, (corners are hard). (but probably figure this out in time)
2) To give the effect of a "slowed drawing(moveing) pixle at a time" without using delay, because i want the user to have "instant access" to Build Times, I want to avoid using FORKs and process, However I have a backup idea if I need to use this delay effect, however i wish not to resort to it.
3) That ability to correctly understand what i managed to do, I'm not sure if my 2D array knows the path or not, since i feel i'm just calling the pathfinding each time, How would I test this out to make sure, cause if theory is correct, using the memorized 2D array is quicker then calling a fcn to find the path over and over, that fcn is best used once per map yes?

-------------
Thanks. (I have read all Zylums recursion posts several times and have a valad understanding of the process, however i have a few kinks i'm unable to solve)

I should also mention the way i solved this problem was using the 2D array of the x,yLOCs of the tiles. It wouldn't make sense to make it check each pixel of that tile would it? so im kinda stumped and was hopeing someone could help jump start my brain thanks.

[A.J]

Like I mentioned in my earlier post, while solving for your path, assign a 'parent' tile to each of the tiles in your path that indicates that tile you have just been on. Then, merely iterate through the parents of your path in reverse order, starting at your last tile, and drawing your line on the way.

[Brightguy]

TokenHerbz @ Wed Nov 17, 2010 1:20 pm wrote:

What I am unable to achieve:
1) to "draw" a line threw the path 1 PIXEL THICK, threw the middle of each tile regardless of directions, (corners are hard). (but probably figure this out in time)
2) To give the effect of a "slowed drawing(moveing) pixle at a time" without using delay, because i want the user to have "instant access" to Build Times, I want to avoid using FORKs and process, However I have a backup idea if I need to use this delay effect, however i wish not to resort to it.
3) That ability to correctly understand what i managed to do, I'm not sure if my 2D array knows the path or not, since i feel i'm just calling the pathfinding each time, How would I test this out to make sure, cause if theory is correct, using the memorized 2D array is quicker then calling a fcn to find the path over and over, that fcn is best used once per map yes?

None of these things require knowing recursion, so I'm a bit confused about how to help. In fact, recursion isn't even necessary for this problem.

Yes, storing the path will be faster than finding it every time (though it might not matter for your application), and it makes sense to use a 2D array to store the path and then check it, though you could also use a 1D array.

[TokenHerbz]

I think i just confused myself, because after writing it down on paper i made it much easier then i was thinking.

the main problem i was having was associating the pixles of the tiles as the actual maze, when it wasn't, so after writing this down, i seen that my path i have is the tiles, and to draw the pixels i just draw them threw the tile of the path, and corner ones and halfs, etc.

anyways yeah, sorry i even posted this i was just confusing myself with thinking i had do so something i never even had to...

Maybe next time i'll try to think it out alot simplar. thx anyways for posts / replys.