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 2 – Nodes

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.

So, what is a node? In the general solution, a node is any point you wish to consider as part of the path from the start to the end. For a while I was thinking that I needed to have a grid superimposed over the whole map, and to block off the squares that had an obstacle in them. This probably works well in a game based in small areas with lots of obstacles, but as you can imagine, doing this in space would need quite a lot of squares… Of course this isn’t what you need to do, you just need to be clever when deciding where to put the nodes. In space there are basically 3 cases you need to consider:

1. There’s nothing in the way
   
2. There is one thing in the way
   
3. There is loads of stuff in the way
   

In case 1 we clearly only need to consider the start, S, and the end, E, as nodes. In case 2 we also need to use S and E, but we will need more. The shortest path from S to E around X would be through a point just to the side of X. If you draw a line through X, perpendicular to the line SE, and then find points on it closest to X so that S could still fit past, you have your nodes.

In case 3, we just need to split up the journey into lots of case 2s. So, find lots of sensible nodes and then find a suitable route through them. Unfortunately every time you move to a new node, you need to recalculate a new perpendicular line through each obstacle. Luckily for me there is a further simplification that I can make as all of my spaceships/obstacles are going to be rectangular[0]. The most sticky out part of an obstacle is going to be it’s four corners, so I can use those as nodes. Actually, so that the ships don’t touch, I’m going to use a distance away from those corners, like this:

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

< Part 1Part 3 >

[0] At the moment at least I am using a rectangular sprite for each ship.

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 >