Jaketastic

Still very primative, but more progress has been made.

WASD, spacebar

P to attempt path solution
R casts a ray at the mouse and shows the first sidewalk.
The enemy will stop if it is to far offscreen.  It helps if you resize the flash window to make it bigger.

To avoid needless backtracking and cut corners when possible, extra tests are now performed each time a way point is reached. These tests  cast more rays at way points further down the list. The furthest way point touched without obstruction will become the next way point and the points in between discarded. Every second or third way point reached will probably need to trigger a completely new path finding solution, because of the time it takes to travel that far.

I’ve added a coefficient of average obstacle size that for now is just a variable, but might (eventually) be set automatically after a few solution attempts. The coefficient helps by hinting when the path should to turn off the ‘sidewalk’. In spaces with small obstacles, you’ll want to get off the sidewalk sooner and the coefficient will be smaller.

It turns out, that a sparse,  empty space is ill suited to the ray casting approach, because it relies on bouncing rays off walls. Luckily, featureless spaces are simple in every other way, and often require no path finding whatsoever.

I’ll need to do some observation and tests to determine what order of left or right turns in a row is most likely to make progress towards the destination.  I’d like to think that a lot of this can be done at runtime, but I need to be careful not to push this project towards the informed sort of pathfinding. I’m determined to keep the AI in the first person. It will have to learn it’s own space by casting ‘learning rays’. A lot of the tests I’ll need to make will be towards finding the important characteristics of obstacle filled spaces, and hopefully finding a few soft rules to follow.

It’s fun to program a solution with such unpredictable results.  As I fly around and press P, I can see the rays cast, but if they were not shown, I’d anthropromophize the behavior of the pathfinding enemy. If the enemy was a bit faster and deadly to touch I think it’d be fun to try outsmart it.

AS3, Flash Game, pathfinding, 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.

AS3, Flash Game, glaze physics, pathfinding