Lost in Space: Part 3 – Distances

This is a 4 part series on how the path finding works in Battlefleet. Please ask in the comments if something doesn’t make sense. Here are parts 1, 2, 3, 4.

You may remember in part 1 we needed to decide what a node’s “distance values” were. Well in A star we need two distances to calculate the distance value, Wikipedia says:

1. The past path-cost function, which is the known distance from the starting node to the current node x (usually denoted g(x))
2. A future path-cost function, which is an admissible “heuristic estimate” of the distance from x to the goal (usually denoted h(x)).

So that’s G, which is the running total of all the distance travelled to get to that node, and H which is an estimate (that cannot be an overestimate) distance to the goal. The total value for each node is the “distance value”, F = G + H.

To calculate G, all we need to do is measure the as-the-crow-flies distance between our current node and it’s parent, PLUS it’s parent’s G.

To calculate H, we need to first decide on a way to estimate distance to the end, without overestimating it. I’m not sure if this applies to all situations (in fact I’m pretty sure it doesn’t if you have grid based movement), but in space it makes sense to just use the as-the-crow-flies distance from your current node to the end node.

So referring back to my in-plain-english description in part 1 when I’m saying distance value, and closest, I mean F. The last thing you need for this implementation of path finding is way of deciding which nodes are next to which nodes. I was going to do a separate post for this, but it’s actually easy; just see if there is an obstacle between the two nodes you are considering, if there isn’t they are neighbours. In the next part you’ll finally get to see some code!

Let me know if any of that isn’t explained well enough in the comments.

< Part 2Part 4 >

Lost in Space: Part 1 – The algorithm

This is a 4 part series on how the path finding works in Battlefleet. Please ask in the comments if something doesn’t make sense. Here are parts 1, 2, 3, 4.

Just as it is in real life, it is important that the spaceships in my game don’t crash into each other. Some 2D games allow units to stack on top of each other, sometimes this is desireable, but in an RTS I think it will only be irritating. You won’t be able to easily see who has the most units in any particular fight.

So, I need two things, firstly to never let units start on top of each other, and second for them not to move into each other. I will eventually write some tests to check that the first hasn’t happened, once I start designing levels. In this post I’m going to cover the second point. When ever a unit is told to move, it needs to be able to calculate a quick route to the destination that doesn’t involve flying through someone else. This is called path finding.

There are lots of different path finding algorithms. After some Googling, I decided to use the A star search algorithm. Here is what Wikipedia says:

function A*(start,goal)
    closedset := the empty set    // The set of nodes already evaluated.
    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    // The map of navigated nodes.

    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)

        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)

            if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset

    return failure

function reconstruct_path(came_from, current_node)
    if current_node in came_from
        p := reconstruct_path(came_from, came_from[current_node])
        return (p + current_node)
    else
        return current_node

It’s not as complicated as it first looks. Basically it says:

1. Start at the start.
2. Are you at the end? If not go to 3, else go to 11
3. Mark this node as checked
4. Make a list of all the nodes that you haven’t already marked as checked, that are also next to the one you were just looking at.
5. For each of those neighbour nodes, calculate the “distance” to it from you current node, plus the distance value of your current node.
6. If that value is lower than the distance value already stored in that node, or the neighbour doesn’t have a parent, store the new value and mark it’s parent as the current node.
7. Add the list you just made to any previous list you had
8. Sort your whole list in order of which one is “closest” to the end
9. Look at the node at the top of the list
10. Go to 2
11. Work backwards from the end, asking each node who it’s parent is

I have written “distance” and “closest” like that because you need to decide how to determine which paths are shorter, and which points are closer, I’ll cover that in a later part. However, before we go any further, we need to decide exactly what a node is.

Let me know if any of that isn’t explained well enough in the comments.

Part 2 >