Solution for finding really closest repair facility

[Emdek]

Have you ever lost unit due to auto returning it for repair and making detour to remote one?
Or were you annoyed by fact that you need wait long for repaired unit to go back to its commander due to fact it chosen remote repair facility?
If yes, then this topic is for you, if no, then it is also for you.

OK, so the main issue is that current behavior is to go to closest repair center, but closest as straight line between two points, it doesn't take into account that selected one could be in fact worst one to choose due to obstacles like cliffs, rivers, walls, units (enemy or own) etc. It's fine for VTOLs, but not for tanks, especially not hover ones (but maybe that part is addressed somehow). The main (and probably the only one) advantage is for sure speed of finding it.

My proposal (posted on IRC few times already, but I'm not sure if really fresh / original) is to use smarter (but also a bit slower to calculate) way:

• choose 10 closest ones using current algorithm (number could be different or depend on some other variables) or using some other heuristic (ideas?);
• calculate how far they are using path finding algorithm and how long it will take to get there using given propulsion, engine power and weight;
• select fastest path and go.

Of course it will take a bit to calculate those values so unit could wait up to 500 ms for results and after that time start going to closest one calculated using current approach (there is big chance that this will be really closest one anyway) and then go to calculated one when results will arrive (from another thread) and decide if it should continue or change target if really closer one is different from fallback target.

We should have clean and separated function with following signature (pseudo code):

Code: Select all

Path findPath(Point from, Point to, Droid* droid, float &length, integer &time)

Where length and time would be references to values to return (unless Path would contain them as values of it's structure, along with list of key points).

[effigy]

The only downside I see to this is if units don't retreat when they should the improved way of getting to the repair facility might end up being useless (assuming that extra wait means the droid gets destroyed).

[Iluvalar]

How bad would it be if the droid was simply redirecting to the closest repair during the route ? So if there is a closest one during the detour, it will redirect on that one instead.

I know that the worst case would be that the tank get stuck in an infinite loop because it's between 2 repair factory that both require a detour to reach like this

R------------
====== |
----X---------
| =======
-------------R

But that kind of scenario are probably extremely rare, and could be easily avoidable by the player I think (one just need to NOT build a repair station in the enemy base ). and that would solve those situations :

R------------
====== |
X------------ R

That frenquently and are hard to avoid by the player.

[Emdek]

effigy, right, so no delay, or first move to "safe place" then, outside of enemy range (could be calculated and used also as value for initial value for that other unit setting) or at least few tiles away from place where it got hit (or hit most of or in most damaging way).

Iluvalar, both cases require the same changes...
And I like dynamic route change, at least recalculate when new facility gets created or existing one destroyed / demolished.

[aubergine]

IMHO we need to split the map in to sectors, and then have cached path finding between sectors calculated at start of game for various propulsion abilities (LAND_ONLY, LAND_AND_WATER, WATER_ONLY, AIR, etc).

The cache would contain the path itself, from a sector to each other sector, or null if the propulsion ability can't get from A to B.

If there are multiple continents in a sector A and B, then paths need calculating for the different continents too. While this could cause quite a bit of data to get stored, depending on the size chosen for sectors, it would massively improve performance of path finding in the game.

So, let's say a sector is 4x4 tiles for sake of argument. On a 250x250 tile map, that would mean 36 cached paths (minimum) per sector, assuming the whole map was flat (one continent). So, lots of data, but only a few megs in total?

When you want to know closest thing it's then a case of:

* get continentA at xA,yA (should be cached on the tile)
* get continentB at xB,yB (should be cached on the tile)
* determine sector A number (simple math based on xA,yA)
* determine sector B number (simple math based on xB,yB)
* cachedPath = sector[A][continentA][propulsion][continentB]
* distanceInTiles = cachedPath.length

So basically you're getting a cached path from A to B for a given propulsion type and then just get the number of points in that path as a rough calculation of path length.You don't need an exact detailed length from A to B, you just need to know roughly which is closer based on the cached path.

Obviously if there are enemies blocking the path that could pose a problem, but because we already know the path we can check for enemies quite quickly too (even if that's done after the droid has started following the path).

Using this approach would result in something so fast and simple that all elements of game logic could readily start making decisions based on paths rather than having to resort to straight-line distances.

The object structure (heck, the whole map data) could be exposed via JS API as well. So, an AI might see that it's usual route is leading to epic fail and then decide to look for other routes - eg. pick random spot on map (to use as a waypoint), find path to that and path to the original destination, then tell it's droids to follow the new path if it's viable (by moving them first to the new waypoint then to the destination).

[Emdek]

aubergine, right, but speed (how long it will take to get from A to B) is even more important factor than length itself.

[aubergine]

So, if sector[A][continentA][propulsion][continentB] is returning an array of path points, then just store a property ".time" on the last array in that matrix.

You can then count the number of each type of terrain along the path, work out the normalised speed (eg. ignoring any upgrades) for the given propulsion to work out how fast the propulsion will take to follow the path and cache the result.

It doesn't need to be super-accurate, it's just a rough (but acceptable) figure that can be used to compare to alternate paths. Remember that the droid might not follow the exact path - it might have to move round minor obstacles along the way, and at a resolution of 4x4 tile sectors the droid could easily be straying either side of the tiles we've got listed in the path.

[Emdek]

Yes, it don't be correct to each millisecond, but would give instant information.
I was thinking about caching only last 10 (or more) calculated Paths, but your solution is better (although will eat more memory).

[aubergine]

I don't think we should worry too much about memory - we'd have to test and see how much RAM it eats up in practice to know for sure. The more complex the map, in terms of continents and terrain types, the bigger the cache will be (and the bigger it's benefit too).

Also, the matrix would be better like this:

sectors[A][propulsion][continentA][continentB]

So you can quickly check if, for given propulsion ability, the droid can get form a continentA to continentB

Instead of the last array in the matrix being null if there's no path, it should just be an empty array (to avoid crufty checks in code that uses it).

Code: Select all

var sA = getSectorAt(droid.x,droid.y); // sector that the droid is in
var cA = getContinentAt(droid.x,droid.y); // continent that the droid is in
var sB = getSectorAt(repair.x,repair.y); // sector that the repair station is in
var cB = getContinentAt(repair.x,repair.y); // continent that the repair station is in
var ability = getPropulsionAbility(droid); // LAND_ONLY, LAND_AND_WATER, WATER_ONLY, AIR, etc

var path = sectors[sA][ability][cA][sB][cB];

Note that in case of AIR ability, the path would allow caching of the "z" coordinates along the path.

Each object in the path array would contain:

* x, y, z
* terrain

[Emdek]

You can simulate this in bare JS, standalone and watch browser / interpreter memory usage.

[aubergine]

Only if I have a map and know the continents and then implement a pathfinding algorithm -- most of that is way beyond my technical ability.

Addendum: Instead of calling the root object "sectors" it would be called "path" (don't know why I didn't name it that to start with lol).

[Emdek]

You can simulate that too, but will be tedious.
Like arrays matrix using numeric value for tile type.
Try on 10 x 10 first and then start increasing it.

[aubergine]

There are some other optimisations that could be used if it's hogging too much RAM.

For example, you start by calculating the path from point A to point B for each sector/continent/ability combination.

At this point you have herds of arrays full of objects like this: {x,y,z,terrain}

You then follow each of the paths to the next sector, and truncate the array at that point and add a "waypoint" object like this {sector} (where value of 'sector' is the alphanumeric id for the sector that contains the next stage of the path).

There is prolly a much more efficient way to do that optimisation.

The result is that each sector contains a stub telling you which sector to go to next to move to a specific destination point B. Once you get to the next sector, you look for the path to point B again.

In terms of working out time, it could be that the time calculation is done at the end of all this, so you work out the time for each stub along the journey, and then starting from the sector closest to destination you work your way back to point A, caching the cumulative time for each stub as you go.

So at point A you can still get time by just looking at it's stub, which is what you need for that fast initial decision making. And then you get the first few points in the chosen path and start following them to get the droid moving quickly. Each time the droid gets to the end of it's path it sees a sector pointer (well, it could be some shortcut ref to a path object maybe?) and grabs the next few points and continues it's journey.

[Emdek]

Yes, binary search tree like (two way linked).

[aubergine]

Yup - I know roughly the concept but my coding skills don't stretch far enough to implement it in an efficient manner. I know just enough to get myself in to trouble lol.

Ooh, think of this from perspective of an AI script... It can now work out, for multiple groups of droids, how long they will take (roughly) to get to a given destination. It would be possible to launch attacks on a location form multiple directions and have them all arrive at roughly the same time.

Addendum: And this would all tie very nicely in to the matrix I want to make as part of the mutator stuff. So remember from another topic I mentioned having quadrants (4x4 tiles) and sectors (4x4 quadrants) - this could all fit in to the same sorts of structures.