Non-tile-based 2D path finding. Part 1

I took some time out to experiment with path finding for a (secret) game I’ve been planning for some time.  Loosely, it’s a 2D platformer with tap-to-move controls.

What I achieved

Before I let on what or how I did it, here is what I achieved so far:

  • Code builds a non-tile based path (navmesh) automatically from the map
  • Determines the closest walkable point to the mouse when clicked

What I did

These are the parameters for these first set of tests:

  • 2D platform map
  • Click on any point for the character to move there (if she can)
  • Character must move along walkable surfaces
  • Character can’t jump (that will probably change later)
  • Non-tile based. Can be any shape or size
  • In Adobe AIR/AS3

I decided to go for a node-based approach.

  • The map is made up of nodes
  • Each node connects to one or more other nodes
  • The character can only move in a straight line between nodes
  • Nodes can be any distance, and any angle apart (e.g. slopes)
  • The character can travel to any point between nodes (doesn’t have to stop exactly on node)

Here is a simple illustration:

  • Character starts on Node A
  • Player taps close somewhere between B and C
  • Game calculates closest point to the tap on the exact line segment between B and C
  • Character moves along nodes until it reaches the destination
  • Player then taps close to Node E
  • Game calculates closest point to the tap on a line segment, which happens to be on Node E
  • Character moves back to Node B which has a connection to Node D, and through to Node E
  • Character does NOT move directly to Node D*

* Note that in the future, with jumping for example, something like this may be possible. But not for now.

path-finding-1

How I did it

Storing the path

The path is stored as a vector (list) of nodes. Each node has a position, some other stuff (that will be important later), and a vector of ‘joins’. Each join is a reference to a connecting node, along with some data to describe the connection (also important later).

Using the example above, the node data may look something like this:

  • A. x=76, y=186
    • B
  • B, x=205, y=172
    • A
    • C
    • D
  • C, x=310, y=237
    • B
  • D, x=226, y=326
    • B
    • E
  • E, x=115, y=310
    • D

Notice that each node has a join back to the previous one too (a join each way). So A links to B, but B also links separately back to A. This is because I want to be able to do one-way paths in the future.

Creating the path

Skip to calculating closest point if you are just interested in the path finding. This next bit is really just an aside, and is very specific to AS3.

I drew the path in the Flash IDE just using the line drawing tool.  I exported the path as a MovieClip symbol so that my code could access it.  The code then uses graphics.readGraphicsData and steps through the vectors to pull out the path. Here are the important bits:

// ### In Main
// Create an instance of my symbol that contains the lines/path
var clip : MyExportedVectorPath = new MyExportedVectorPath();
// Create a path object (the object that does all the heavy lifting)
path = new Path();
// Pass in the lines so that the code can rip the nodes/joins
path.buildFromClip( clip );

// ### In Path.buildFromClip
// ### ... this is just a snippet ...
// Grab all the graphics data from the symbol instance
var graphicsData : Vector.<IGraphicsData> = clip.graphics.readGraphicsData(true);
// Step through the graphics data
for (var i : int = 0; i < graphicsData.length; i++) {
    // If we have found a path (i.e. a line or series of lines)...
    if (graphicsData[i] is GraphicsPath) { 
        var path : GraphicsPath = GraphicsPath(graphicsData[i]);
        // Step through all the commands that make up the line(s)
        for (var j : int = 0; j < path.commands.length; j++) {
            // If the command is 'MoveTo' then we are creating a new node somewhere without creating a join
            if (path.commands[j] == GraphicsPathCommand.MOVE_TO) {
                // Handle creating a new node, or grab the node
                // at this location if it already exists
            }
            // If the command is 'LineTo' then we are creating a join between two nodes
            else if (path.commands[j] == GraphicsPathCommand.LINE_TO) {
                // Handle creating a join to another node. It'll
                // either be a new node or an existing one at this
                // location
            }
        }
    }
}

Calculating the closest point

This is the first part of the actual path finding. In my implementation, the user taps on the screen (or clicks with the mouse) and the closest walkable point to the tap is found.  This is done like this:

  1. Iterate all line segments (joins) in the map. Because each join is usually there twice (A to B, and B back to A) make sure you do each one only once
  2. Find the closest line segment to the tap
  3. Find the point on the closest line segment that is closest to the tap

Here are the methods I use (I have them in a class called GeometryUtils).  They are three relatively simple and related methods that I sourced elsewhere on the net, starting from this stack overflow.

/**
 * Calculates the distance from a point to the closest point on a line segment. TIP: If comparing
 * distances between more than one line segment and a point and you don't need to know the actual
 * distance, use relativeDistFromPointToLineSegment instead (faster).
 * @param	segA	First point on line segment
 * @param	segB	Second point on line segment
 * @param	p		The point
 * @return			The distance to the closest point on the line segment
 */
public static function distFromPointToLineSegment( segA : Point, segB : Point, p : Point ) : Number{
	var dp : Point = new Point(segB.x - segA.x, segB.y - segA.y);
	var something : Number = dp.x*dp.x + dp.y*dp.y;
	var u : Number = ((p.x - segA.x) * dp.x + (p.y - segA.y) * dp.y) / something;

	if (u > 1) u = 1;
	else if (u < 0) u = 0;

	var dx : Number = (segA.x + u * dp.x) - p.x;
	var dy : Number = (segA.y + u * dp.y) - p.y;

	return Math.sqrt(dx*dx + dy*dy);
}

/**
 * Calculates a weight (not an actual distance, just a representative number) between a point an the
 * clostest point on a line segment. This is used to compare lots of line segments with a point and
 * determine which is the closest.
 * TIP: If you need the actual distance, use 
 * @param	segA	First point on line segment
 * @param	segB	Second point on line segment
 * @param	p		The point
 * @return			A value representing relative distance from the closest point on the line segment
 */
public static function relativeDistFromPointToLineSegment( segA : Point, segB : Point, p : Point ) : Number{
	var dp : Point = new Point(segB.x - segA.x, segB.y - segA.y);
	var something : Number = dp.x*dp.x + dp.y*dp.y;
	var u : Number = ((p.x - segA.x) * dp.x + (p.y - segA.y) * dp.y) / something;

	if (u > 1) u = 1;
	else if (u < 0) u = 0;

	var dx : Number = (segA.x + u * dp.x) - p.x;
	var dy : Number = (segA.y + u * dp.y) - p.y;

	return dx*dx + dy*dy;
}

/**
 * Returns the point on a line segment that is closest to a given point.
 * @param	segA	First point on line segment
 * @param	segB	Second point on line segment
 * @param	p		The point
 * @return			The point on the line segment closest to the given point
 */
public static function closestPointOnLineSegment( segA : Point, segB : Point, p : Point ) : Point{
	var dp : Point = new Point(segB.x - segA.x, segB.y - segA.y);
	if ((dp.x == 0) && (dp.y == 0)) return segA.clone();
	var something : Number = dp.x*dp.x + dp.y*dp.y;
	var u : Number = ((p.x - segA.x) * dp.x + (p.y - segA.y) * dp.y) / something;

	if (u > 1) return segB.clone();
	else if (u < 0) return segA.clone();

	return new Point( segA.x + u * dp.x, segA.y + u * dp.y );
}

If you read the comments in the code you’ll notice that you can use distFromPointToLineSegment or relativeDistFromPointToLineSegment.  The first returns the actual distance and is used if you need the exact distance. The second actually returns the square of the distance (leaves out the square root for speed) which is ok because we don’t actually care what the distance is, as long as we can compare it to the other line segments.

So my code does something like this:

// Iterate all nodes
for each (node in nodes){
    // Skip nodes that have been checked, then flag this one as checked
    if (node.checked) continue;
    node.checked = true;

    // Iterate all line segments coming off this node
    for each (join in node.joins){
        // Calculate distance to tap (Point)
        d = GeometryUtil.relativeDistFromPointToLineSegment( node.position, join.otherNode.position, tap.position );
        // If this is closer, remember this one
        if (isCloserThanWhatWeHave( d )){
            // Remember this one
            rememberClosestSegment( d, join );
        }
    }

    // Now we have the closest segment. Find the point closest to the tap
    point = GeometryUtil.closestPointOnLineSegment( closestJoin.node.position, closestJoin.otherNode.position, tap.position );
}

Note that most of the work of finding that last ‘point’ using closestPointOnLineSegment is already done during the relativeDistFromPointToLineSegment function call. If you take a look at the definitions for these two functions you’ll see there is basically only one line different. At some later point I’ll update my code to make use of this optimisation.

What it looks like

So this is what the path looks like in the Flash Professional IDE when I’m building it. I placed a screenshot of Mark of the Ninja in the background as a pretend level, just because. The green lines are drawn using the line tool, and are automatically converted to nodes and paths (see Creating the path above). Just ignore the purple markers and red lines around the door for now. That’ll come later when we manipulate nodes (to open/close doors etc).

Building the path

Once the code extracts the path, it draws a representation to the screen.  Tapping anywhere will find the closest point using the technique described above and place a yellow marker on it.  If you have the flash player you’ll be able to click/tap below to try it, otherwise you’ll just see a static image.

If you have Flash Player 11.6, click below to see the code in action –

Next

Next phase, find shortest path from the last tap on the map to the next one (the actual path finding part!)