FAForever
Allocate a pathing number to each part of the map
Allocate a unique number for each pathing type to each part of the map, with all parts of the map that can path to each other having the same number.
For example, with the map Pelagial v2, there are various islands scattered around that are pathable by amphibious units, but not by land. Each island should therefore have a different 'land' pathing number to each other island; however, they should all share the same 'amphibious' pathing number.
By illustration, the below colours each location that has a different land pathing number with a different colour (although I cycle through the same 8 colours so there's some repetition):
For an example of a use case, this could be used for identifying plateaus and determining how valuable they each are - using the above, you could create a table with the amphibious pathing group numbers for locations that have a certain number of mexes and which don't have an enemy start position occurring in them, and use this to decide where to send a transport.
For reference, M27AI currently achieves this by cycling through every 'cell' on the map (1x1 size on smaller maps, 2x2+ on larger maps) and determining if it can path to the adjacent cell, and then keeps cycling through to map out the entire area that can be pathed to from that single cell. It then records a table with X and Z keys, which will contain the pathing number assigned (with all of those cells assigned the same pathing number). It then increases the pathing number by 1, and goes to the next cell and repeats the process. The end result is that if given any x and z value you can check what the pathing number is in the table. The main part of the code that does this is: https://github.com/maudlin27/M27AI/blob/ce2a59ad4a0be464562ae810efee78bb7a09a4ea/lua/AI/M27MapInfo.lua#L3304
However, I'm hoping there might be a way of achieving this that is as quick to query in real-time, and as accurate, but without needing such a massive amount of RAM (as M27 currently has table sizes of up to 512 x 512, i.e. 262k entries for each pathing type)
Just to expand on this as my AI does something similar. Leveraging the default path markers, each is assigned a graph area depending on connected markers. All markers that can be connected to each other is assumed to be on the same graph area.
So a map like open palms would have 3 graph areas. one for the main part of the map and 1 for each plateau. A map like twin rivers would also have 3 graph areas. The map like in the issue above would have around 21.
This is already implemented with #4270 , each unconnected area has a label assigned to it. It is the foundation of the function CanPathTo, see also:
- https://github.com/FAForever/fa/pull/4270/files#diff-54afb8d1e2391054af22d032f5ee6fad652b7a99d5ec28ff484a907efbd0f74eR34
- https://github.com/FAForever/fa/pull/4270/files#diff-27f81f4cd655fe55438dd405e819b00d616deec749f850daeee0ad0f836e975dR189 with https://github.com/FAForever/fa/pull/4270/files#diff-27f81f4cd655fe55438dd405e819b00d616deec749f850daeee0ad0f836e975dR478
At the moment there is no drawing function for that yet, but with thanks to Fichom we do have a button for it. Tomorrow I'll see if I can find the time to implement the drawing function, then I'll share some screenshots to confirm that it is indeed what you are requesting.
edit: in terms of memory and performance - the navigational mesh uses a compression tree (similar to a quad tree) that saves significant amounts of memory. It also allows for constant time retrievals. Therefore the function is as cheap as yours in M27 to perform, but it is significantly less heavy on memory.
This is precisely what the GRAPH NAME was meant to do - except they ended up defaulting all markers from the same GRAPH to the same GRAPH NAME, effectively nerfing the data structure. The fix to the 'CanGraphTo' function was simply checking connection from one marker to another - and if connected - they were on the same graph and recording it in the markerlist - if not connected - it would get a new GRAPH name. As follows;
GRAPH (LAND) -->> GRAPH NAME (DefaultLand) --> MARKER NAME (Land27) --> MARKER DATA (position, etc)
This structure, if properly populated, would allow CanGraphTo to instantly tell if two points are pathable, without the work - but no, the map editors don't have this ability, so they end up defaulting all the GRAPH NAMES to 'Defult'..layername. So sad.
Here are a few examples. I think this is exactly what you were describing @maudlin27 . You can query this using CanPathTo.
This structure, if properly populated, would allow CanGraphTo to instantly tell if two points are pathable, without the work - but no, the map editors don't have this ability, so they end up defaulting all the GRAPH NAMES to 'Defult'..layername. So sad.
Yes, it is sad - I agree. But luckily no more