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