Heuristic, semi-informed, realtime-adaptive 2D pathfinding using ray casting.
Despite it’s being a gawd-awful mouthful to describe, I’ve attempted to heuristically develop a real time, semi-informed, pathfinding technique using the ray casting in the 2D glaze physics engine for Flash AS3. Pathfinding in games is usually accomplished with a waypoint network or navigation mesh, and a little algorithm called A*. These techniques work great, but I don’t want to bother with constructing nodes for my maps, and I wanted an excuse to mess around with the ray-casting built into glaze, so I approached the problem from, (ahem), a different angle.
The problem is how to get the enemy to the player while the player is moving and obstacles (possibly moving) are in the way.
I’ve gone pretty easy on myself for the requirements of this particular pathfinding problem. The path finding solution can be wrong if the enemy’s behavior will look unexpected, unpredictable and interesting. The path can fail entirely and it can be interpreted that the enemy does not see the player or cannot perceive how to reach it until conditions change. Learning the weaknesses of the pathfinding algorithm becomes part of the challenge of the game.
The first step in my path finder is a ray cast in the direction of the destination. I then use the line perpendicular to the normal of the first obstacle obstructing the ray. This line follows the obstacle like a sidewalk until it encounters another obstacle, where another 2 rays are cast. One ray along the next sidewalk, and the other in the direction of the destination. If the ray cast in the direction of the destination is obstructed, a waypoint is added. This process is repeated a few times until the destination ray is unobstructed or the algorithm gives up. The enemy then follows it’s waypoints to the destination, checking at each waypoint to make sure the player is not in line of sight.
Anyway, here is what a very rudimentary, and buggy start to a heuristic pathfinding algorithm using ray casting looks like:
Keyboard Controls:
Move = W, A, S, D
Shoot = SPACEBAR (if you kill the blue enemy you have to reload)
Press “P” to attempt to get Enemy Pathfinding solution…
Cast ray from ship to mouse = R
Amazingly, walking along the sidewalk and only taking right or left turns can sometimes get you in sight of your destination. More analysis is forthcoming.
I’ve had some great ideas for path finding with ray casting. Please email me if you’re still interested. I keep getting distracted with other things but really want to work on it.
Note* the background for this textbox is black (just like the text), so it is not very easy to see! I had to change the color with firebug (local change only don’t worry).
Of course I’m super curious to see someone else’s ideas on path finding with ray casting! And thanks for the heads up on the black text! Seems to not be a problem in firefox – which is why I missed it.