Find Minion with shortest path

Question

I'm working on a game like Settlers III/IV. There are buildings which produce goods which have to be gathered by carrier units.

I have to find the carrier with the shortest path to collect the goods. So far, not a big deal. I simple do a expanding circle, starting from the production building, and choose the first carrier found due it has the shortest direct way.

If this carrier can't reach the building (e.g. is on another island or so), the search goes on.

But now take a look at my awesome paintskills. The black line is an obstacle which my minions can't get over. Red lines are direct paths, blue is absolute path.

The first carrier is A, but it's direct way is blocked. Second is B, direct way blocked as well and third, C, has the longest path of all.

As you easily can guess, I want to sent B due it has the shortest absolute path.

What's the lowest affort do determinate if a carrier with blocked direct way has a shorter way then a carrier with a longer direct way?

I'd love to have some lecture about that, but I only was able to find (a lot) of pathfinding where the unit itself searches the path, not the target searches the unit with shortest path.

Edit: Simply trying out until the minion with shortest path is found is no solution. I don't want to make it stuttering on a i7 or so. Settler 3 is a 17 years old game and somehow they have implemented such a functionality without needing over 9000 gigahertz. If you have any idea which involves routing tables or whatever, I'm happy. Goal is simply to find the minion which could arrive as fastest, in the shortest time possible. Not a big deal if therefore 200mb of routing table have to be generated or whatever.

Answer 1

You could use Breadth First Search or Dijkstra's Algorithm to find the paths from the building to all carriers. I have a demo here of a related problem. Once you find a carrier, stop; that's the closest one to the building (taking into account walls etc.).

Breadth First Search can be quite fast. Dijkstra's Algorithm is a little bit slower but it can handle varying movement costs. It's very much like your expanding circle idea; run the animations on my page to see how it expands in all directions, but can also go around walls.

Answer 2

You have almost answered your question in your post. You say that you

simple do a expanding circle, starting from the production building, and choose the first carrier found due it has the shortest direct way.

So this should be your initial point, the production building. You do not need to cycle through all of your idle minions to get the nearest one, instead you can start searching for the idle minions around your building and stop whenever you find one.

Having no idea how your map and pathing models are setup, I would assume that you have some kind of two-dimensional array as a map, with XY orientation and elements meaning what type of object you have on the map. Buildings, trees, roads etc. Minions and other "moveable" objects go in separate array with just XY coordinates for their position.

If this is your case - you can just send a wave from your production building and see which idle minion it arrives first. It would be your nearest idle minion.

If you don't have this, and you have XY coordinates system, with the list of the objects on the map and their XY coordinates, widths, lengths, shapes, etc. then it's going to be painful.

If your map is huge and sending a wave will lead to significant calculations and slows down the system, if your map and objects on it are 'indestructible', 'immovable' etc. you can build up hashtable with the shortest paths or just lengths of the shortest paths from any-to-any points on the map. There would always be no more than n*(n-1)/2 elements in your hashtable, where n is total number of the 'map-squares'.

If your map and objects are changeable, you still can build up such hashtable and update only the part, where your changed points belong to. Consider you build new building on the tile (x=10, y=15), meaning that you need to update only paths for the pairs of points, which shortest paths lead through this point.

Having such a table, you can easily get all the paths starting from the point where your production building stands, sort them by lengths, join with the points where your minions stand and get the one with the shortest path.

I know, it all sounds like you need to build some path-finding engine from a scratch, but when you do it you know it's got to work perfectly.

Answer 3

I don't known if you've solved the issue since the question was posted, but how do you expect to know which is the carrier that is closer to the building at a given time, if you don't know their shortest path? It does not make sense. You need to calculate some sort of path-finding between building and carriers. And just after that, select the closest carrier. There is no logical way of selecting the closest before knowing how much close they are.

I'd love to have some lecture about that, but I only was able to find (a lot) of pathfinding where the unit itself searches the path, not the target searches the unit with shortest path

You see, there is the confusion. The two things are the same: path-finding. The only difference is that, you are right, there might optimizations for the case when you have to run it for multiple agents (e.g. carriers) but the target is the same for all of them (e.g. the currently selected building). It is still the same path-finding, but just optimized.

I will get into that shortly, but first let me just comment as a disclaimer that you are assuming just too fast thatthe a game from the 1990s was not using path-finding for doing the job you want just because of older computers. It is actually quite likely that it did use it. You over-estimate the CPU cost of path-finding and under-estimate its use in the past. Even older games employed path-finding fora bunch of objects.

That said, here is one way of optimizing the path-finding for the situation when the target is the same for multiple agents:

1) it can be simply called the "early exit approach". Sure, if you are testing path-finding for 10 carriers in relation to a given building, one of the end points of the path will be always the same: the building's position. And you are right: there is something you could do with that particularity of your problem that will help you immensely.

The process is the following. Suppose you have to try 10 idle carriers. So, you run a path-finding algorithm for the 1st and then finds the shortest path from that 1st to the building and save it's length (in terms of number of tiles, not in direct straight distance). Now, you start doing the path-finding for the 2nd. Whenever a path being evaluated gets bigger than the saved one, you stop and exit its evaluation. If it ends up being shorter than the saved one, then you of course substitute the former saved one by this new. You then move on to the next carrier. So forth and so on.

Depending on how you implement that and your map is, then yes, it can give you a great performance advantage, because you can stop evaluating carrier's paths faster.

Now, keep in mind that in all and any well-implemented path-finding, you have a couple of other optimizations that you should always consider.

2) search less: just by filtering out the non-idle carriers, you decrease significantly the number of objects to path-find.

3) search in fewer places: spatial partitioning is a god-sent. You can (and actually almost always should) divide your map into areas (squares, irregular areas, whatever). Then, the first thing is to detect which carriers are in the same area as the building (or in same area + neighbor areas). And these are the carriers you wanna path-find, not all in the map. This technically is the very basic optimization for any path-finding. Although people frequently forgot about it, it has been around in the game industry for quite a long time actually.

As a bonus, keep in mind that nowadays open-map games usually use nav-mesh for path-finding, instead of tile-based grids:

4) nav-mesh - no matter if your building game uses square tiles, hexagonal tiles or whatever, if your game can have nav-meshes built on the fly, your path-finding for a building game like yours will probably be very, very cheap, in comparison to any tile-based solution (squared or hexagonal).