The situation is two entities on a grid that want to meet in the middle, I though of a few solutions to this but all have one problem or more.
the first solution I came up with is calculate a path from one to the other and send that path in reverse to the other entity, but the problem is my travel from hex to hex is asymmetric, going up and going down an elevation have different rules so a path in reverse can be invalid. that solution goes in the trash unless I change the movement rules.
the second solution I though about is picking a hex in the middle and navigating independently there, and that works great as longs as the hex they are trying to navigate to can be reached from both entities, and I can’t check that without trying to path there.
Image attached demoing a scenario where they can’t path to the hex in the middle of them.
the only fail safe solution I can think of is having one entity wait in place and the other walking over, but that has its own problems, wastes time (if they meet in the middle only half the travel time) and doesn’t look and feel right in a atmospheric sense(why is always only one guy walking? -player) to name a couple off the top of my head.
Anyone has any idea to make the first or second solutions workable?
A new solution I didn’t even consider?
Thanks for reading!
I’m a bit rusty on A*, but maybe you could return the list of the closed paths from both entities, sorted on the highest score and see if the other closed entity contains that tile. If it does, both can reach that tile and start walking there. I would start there. This would mean that sometimes one entity would stay still based on elevation and one walking, but it should be the shortest route right?
So you’re saying use the first solution i suggested and if the path isn’t crossable at some point from one side just let the entity wait there because the other one will have a valid path there.
I like that, that covers most scenarios pretty good, could maybe look a bit awkward at rare times but it should be fail safe.
thanks buddy
Not completely like solution 1, but sort of. If you keep a reference to the shortest paths including unsuccessful ones and check against the other entitys shortest unsuccessful (eventually leading to the path calculated by the a* for one entity), you’ll get the shortest route. Might be the one calculated by the a* or might be a partial path both can travel to meet at one destination. But all in all, you get the idea yes
I got the mindset yeah, but I don’t follow your suggestion itself…
what do you mean “shortest paths”? each entity has one path returned to it when seeking to path to a destination, the pathing algorithm doesn’t create any extras either.
if each one calculates an independent path to the other they can miss each other entirely on the way and effectively just swap places, I don’t want to calculate a new path each “step” they take.
I do have a way to add new tile to a path if a target moves(used by a chase mechanic), but I don’t see how that would help here.
I might be overthinking it for what you want done and might not be as efficient. I’m suggesting not only keeping the final path for the entities and walk that way, but keeping the tiles that had the shortest paths too (the “closed” paths) and see if any of their closed paths matches a tile.
If we use your image as reference, lets consider that the entities can walk down cliffs, but not up, the shortest path returned for each entity would be to walk around the ravine to eachother, but the shortest path would be to check that both could meet up at the tile down in the ravine (your red lines), because both can reach that tile and its the shortest way to meet up by combining that route
Yeah that’s the thought behind the second solution, but it’s not fail safe unless i do a whole bunch of various checks seeing if the destination is valid at all.
This needs to run on many entities so I don’t wanna load it up with complicated logic.
Yes, there’s definitely extra overhead there so you some extra checks would be needed as you say, but i would say that it’s failsafe unless there’s no solution, but it could also become heavy considering mapsize etc. It was just a suggestion, don’t know your scope and how efficient it needs to be, how often it runs and so on. Your countersuggestion seems like a good middle-ground
The simplest solution to this is to not use A* at all. Instead do a flood-fill to mark the distance of every hex in the grid to each agent. If you’re writing custom code for this, you can fill from both agents at once, so on the first iteration you find all the hexes 1 step away from each agent, on the next iteration all the hexes 2 steps away from each one, etc. At some point you will hit a hex that is a known distance from both agents, at which point you stop and trace the shortest path back to each one (by walking down the distance gradient). But if you want really simple (or your map is small), you could simply fill the entire map with distances from one agent, then the other, and then pick the hex with the smallest maximum (of the two distances) as your meetup hex.
If you want to make it more efficient, then instead of simply flood-filling, you could actually do A* from each agent towards the other. The trick is that in this case you have to do the A*'s simultaneously. If your A* code is written in such a way that you can do one step at a time, then just do that: one step of A* for agent A, one step for agent B, and repeat until you find a hex that is a known distance from both.
hmm… I suppose doing some ungodly creation that sits between A* and the original Dijkstra and searches from both ends in this fashion can be cool.
really interesting solution, if not here I’ll definitely try and do something like this at some point.
I thought about baking some pathing information into the grid, but the map size is giant (easily over 1000x1000) and the number of entities that need to do such a thing is can surpass 100k (obviously not everyone is doing is calculation all the time, but still), and a huge variation between movement rules for each “type” of entity, make that whole thing dynamic(terraforming the terrain) and it just becomes a huge counterproductive headache imo.
One thing that pops into my mind is going for something similar to the flow-field per @JoeStrout 's suggestion, but also getting a bit inspired by the “jump point search” optimisation for A*. Instead of flood filling outwards, fill in directions which are more likely to reach the target location (ie: the other agent, or the closest other point they’ve searched).
But with thousands of units this isn’t tenable. Honestly, I’d figure out a way to bake whatever I could.
Based on my own experience having done so in the past, I’d consider having a node graph separate to the game’s grid. You don’t need anywhere near as many nodes as you have grid cells and they can easily cut out huge chunks of work. Eg: if two nodes are not connected you don’t have to bother checking thow he unit specific rules apply to the cells between them because you already know it’s irrelevant. And because they’re much more sparse you can have multiple node graphs if it’s relevant, eg: one for walking units and another for water units.
In other words, use the node graph to quickly calculate a rough path and/or meeting point. Then have the units make detailed paths from each node to the next as they arrive. If things can change en-route that might even get you a better result (eg: you spend time calculating a path through a distant field only for it to get bombed, and now you need to re-calculate it anyway). And it can give a nice “natural” looking result because units don’t respond to specific details until they’re close enough to “see” them (eg: they don’t end up going the long way around things to avoid obstacles they couldn’t have known about yet).
