In the last two days, just to see if I could do it, I wrote up a pathfinding algorithm that uses the collision detection map type I use for my RPG. I managed to pull it off to some extent.

What mine does, is take the location of a black dot on a collision map, and search out paths, using a ghost coordinate set, that moves around following this direction priority: Up, then down, then left, then right, and then last, but not least, backtracking(To eliminate dead-ends). The ghost coordinates keep searching out a path until they are the same as your coordinates(The white dot on the collision map), then moves the black dot to the first step of the path that leads it to the white dot without any backtracking. It works with any collision map using my system for such, providing that there is an actual path between the black and white dot.

At the moment, it does NOT choose the best path. It merely chooses a path that works. I have an incrementing variable in the algorithm intended to fix this, but it doesn't serve its purpose yet.
It also is INCREDIBLY slow. I'm pretty sure the reason for this is that it checks all paths until one touches the white dot before EVERY move. I figure I could cut the checking short once it eliminates all moves from the current position except one, but I'm not sure how I would.
And... While the path searching ghost coordinates will always find the white dot, the actual black dot can get stuck moving back and forth between two spaces, such as in a space configuration like below:

Code:

XXXXXXX
X  O  X
XXXOX X
  X
  X XXX

X=Block O=Endless loop spaces


I dunno if anyone think they can help me with it, but if anybody'd like to see the actual code, I'll go grab it.
Code for this would be helpful, might see some optimizations you could pull off, might speed it up some.
It's probably a bit messy, I used a bunch of colons instead of new lines because it saved lines(Which with the Prizm's text wrap, is annoying).


Code:

'ProgramMode:RUN
147->Dim List 2
{4,147}->Dim Mat A
A->G:B->H:A->K:B->L:0->I
Lbl 1
Locate M,N," "
Locate G,H,"_#E6A4_"
If G=X And H=Y
Then P->A:Q->B
Goto 3
IfEnd
List 1[(H-1)*21-(21-G)]->C:List 1[(H+1)*21-(21-G)]->D:List 1[H*21-(21-(G-1))]->E:List 1[H*21-(21-(G+1))]->F
If C=0 And Mat A[1,H*21-(21-G)]<>1
Then G->M:H->N:1->Mat A[1,H*21-(21-G)]:H-1->H:1->Mat A[2,H*21-(21-G)]
Goto 2
IfEnd
If D=0 And Mat A[2,H*21-(21-G)]<>1
Then G->M:H->N:1->Mat A[2,H*21-(21-G)]:H+1->H:1->Mat A[1,H*21-(21-G)]
Goto 2
IfEnd
If E=0 And Mat A[3,H*21-(21-G)]<>1
Then G->M:H->N:1->Mat A[3,H*21-(21-G)]:G-1->G:1->Mat A[4,H*21-(21-G)]
Goto 2
IfEnd
If F=0 And Mat A[4,H*21-(21-G)]<>1
Then G->M:H->N:1->Mat A[4,H*21-(21-G)]:G+1->G:1->Mat A[3,H*21-(21-G)]
Goto 2
IfEnd
Lbl 4
I-1->I
If List 2[H*21-(21-G)]=1
Then H+1->H
Goto 1
IfEnd
If List 2[H*21-(21-G)]=2
Then H-1->H
Goto 1
IfEnd
If List 2[H*21-(21-G)]=3
Then G+1->G
Goto 1
IfEnd
If List 2[H*21-(21-G)]=4
Then G-1->G
IfEnd
Goto 1
Lbl 2
If List 2[H*21-(21-G)]<>0
Then M->G:N->H
IfEnd
N=H+1=>1->O
N=H-1=>2->O
M=G+1=>3->O
M=G-1=>4->O
I+1->I:O->List 2[H*21-(21-G)]
If I=1
Then G->P:H->Q
IfEnd
Goto 1
Lbl 3
Locate K,L," "


ANY Locate command inside, except for the final Locate space that acts as an eraser, is there strictly for debugging purposes(Mainly showing me the location of the ghost coordinates).
The collision map and movement for 'you' are in other files, but those have no problem and are heavily optimized already, as they are stripped down versions of RPG files.
I have a few suggestions which might help (they are algorithmic rather than dealing with specific code):

- To avoid the endless loop, you could store the direction last used along with coordinates in your back-track list (stack)
- Once you have been able to reach a location (ANY location) with some path, mark it so that you do not try it again with another path later (kind of like a "fill" tool in a paint/draw program).
- You are using a depth-first search, meaning that you go one direction, try all possible outcomes for it, and then try it all over again with the other directions. That is a 4^N problem (no wonder it takes so long)! I suggest using a breadth-first search, meaning that you take one step in EVERY direction and see where you can get; and then take another step from all those locations and see where THOSE can get; etc., until one of them touches the point you are trying to get to. If you do this FROM the target location TO the starting position, then the first adjacent location to touch the starting location is the location to move to next Smile
- With either technique, one thing you could do to save time (at the cost of SOME intelligence of the movement) is to find a good path, and then follow it for a few steps before searching the path again. You would want to decrease the number of steps to take as you get closer though, or else you could get REALLY close but keep on going because the thing being chased has moved; so you could, for example, move a "tenth" of the distance (in steps) along the currently selected path each time.
Although I'm probably stating the obvious, have you explored Wikipedia's Pathfinding article, which presents a fairly straightforward and very not O(n^2) algorithm for the task? Their results more or less approximate the steps that shkaboinka suggested.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement