A different approach to path finding.

I spent the last week working on jStar. After researching and working with a* for the last few days, I came to the conclusion that while very powerful, it was slow and overkill for my arcade-adventure, shoot the robots game. Also, since the player is constantly moving, the recalculations using the recursive path finding approach was killing my frame rate. I will explore more on this later, but I basically threw every thing I was working on to the side and set out to create my own path finding routine.

I started with these constraints:

1. I don’t need 360 degree movement, my enemy robots only need to move up, down, right left. For this reason, even 8-way a*. is a little too much power for my use.
2. Actual collision detection between the enemy robots and the walls is time consuming and difficult. If I can eliminate the need, it would speed up the routine significantly.
3. The robots can be intelligent, but they don’t need to be smart, remember, they are robots.
4. The grid squares for the robot movement must be large enough to hold an entire enemy robot. That would mean completely changing both my grid and my sprites. I thought maybe a complete over-head perspective would suit this fine.
5. I would need to create a specific, invisible path that the robots can walk on, eliminating the need to a* like calculation, and collision detection between robots and walls.
6. The path should be drawn so there are always 2 tiles that the robot can move to from the current tile.

I took these new constraints to the computer and sat down to write some pseudo code. Here is what I cam up with:

If Robot Not Moving then
	check to see what CURRENT TILE the robot is in
	check the tile UP, DOWN, RIGHT, LEFT tiles from CURRENT TILE
	if a tile is on pre-determined ROBOT PATH , push it to movement stack (this should always result in 2 tiles)
	Compare the two tile by taking the absolute value of the different between the x and y positions of the tile
	and the x and y positions of the player.
	Which ever produces a lower number will be the CRITICAL path on the pre-determined movement path.
	set Robot Moving Boolean to True
	Add the the delta to the movement x,y for the robot for the next frame
	Before moving the robot, check to see if it was made it completely inside the destination path square
	if so, stop the robot set Robot Moving Boolean to false
end if

That’s basically all there is to it. You can test this completely new and very basic looking overhead version by clicking the link below.
Use the arrow keys to move the green circle with the “P”. The Red Circle with the “E” on it is the enemy and he will attempt chase you on the path.
See jStar in action

Obviously, there are a few things are left out. The first one is the robot’s ability to fire a missile at the player when within range. The second is collision detection between the robot and the player. Lastly, if I want to use the “berserk-like” perspective I have already put hours into designing, I will have to modify this engine. Those are my next steps.

If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.