The AI will find you! (pathfinding video)

[Uveso]

While debugging the AI pathfinding functions i wrote some debug code to show the AI paths.

Bridgepathfinding.png (385.77 KiB) Viewed 2470 times

If you want to see how the AI is using waypoint markers; here is a small video (5 minutes):
https://youtu.be/PkyWgCWqC8w

[nine2]

How do you programatically draw lines? Can I draw my own lines in a real game?

[nine2]

How does the game deal with it when there are no markers? If it generates them it would be interesting to see that

[Uveso]

Code: Select all

DrawCircle(MarkerPosition, 5, markerInfo.color)
DrawLinePop(MarkerPosition1, MarkerPosition2, markerInfo.color)

Basicaly its working with a ForkThread like this:

Code: Select all

    while true do
        DrawPathGraph() -- this function is drawing all lines we need.
        WaitTicks(2)       --if you wait 3 ticks, then the linedrawing will flicker

    end


Sometimes you need to use WaitTicks(1) on fast PCs. (fps over 60)
If the game runs with 60fps, then we have 1 frame every 16.7 milliseconds.
WaitTicks(2) is waiting 20 milliseconds.
Now, if we wait 2 ticks/20 milliseconds, and the game creates a frame every ~17 ms,then we have already a tiny flickering every 7 frames.
(at least for 3,3 milliseconds -> (20 - 16,7))


If the game has no markers it will use the c-engine command CanPathTo(pos).
This will also find a path but it's way slower then using the graph with Markers.

I have already experimented with auto generated waypoints.
Well. hard to say if we get this to an beta state. Maybe possible on 5x5 maps.

- I created a grid for a 20x20 map with about 5000 nodes.
- Checked the path between all adjacent nodes.
(I used GetTerrainHeight() and GetSurfaceHeight() to scan the way on every pixel between 5000 x 6 nodes. (30000 connections)
- Removed all nodes that are near hills.
- Removed all nodes that are connecting the same point twice.
- Genreated paths between all startlocations and massmarkers.
- Removed all nodes that ar not needed for a path.
- After this i had about 150 nodes for pathing.

But the calculation time was on my i7 ~1.2 minutes and there where many pathing errors on different maps.
I don't say its not possible, but we won't get this in the near future.

[nine2]

thanks for the tips.

regarding ur slow algorithm... you could run it offline and bake the paths into the map as real markers. then it could be more complicated, higher quality, faster execution. however u would need by-in from Slack gods plus i dont think its worth it. ai sucks

[Uveso]

Autocreated markers can never be as good as markers set by mapper/modder.
And it's faster to create new markers from the scratch then modify markers that are autogenerated.

At the moment i can only generate amphibious paths by extracting nodes from existing Land and Water markers.
Also AIR paths are autogenerated with a simple 8 way grid.
(note to Map-Authors who don't make AIR markers: We need markers for AIR not to find the destination. We need them to avoid dangerous areas on the way to the destination !!!)

Maybe we can open a new forum section for modders who are interested in making map markers.
(I plan to make the AI pathing like in the video accessable per gameoptions. So the author can test and "see" how(if) the markers work.)

But this will not happen today

Let me first finish the AI bugfix and my own AI. Should be done in April.

[Sprouto]

As a fellow AI modder I look forward to your work Uveso.

As a suggestion - for air markers - you can use a very standard 16 x 16 mesh of air markers for every map. Why 16 x 16 you ask ? (Uveso likely knows this already but this is for the general audience). Well - this aligns exactly with the threat map. Other than that, air units will find their own way to a target with little need for fine path markings. That way, you can have a standard grid which you just import to every map - and voila - job done - at least for air markers.

In simple terms, the threat map is like a checkerboard - and the game keeps track of threat on this checkerboard. Therefore, the air markers are simply there to help the AI path around those which have threat levels that might be too high. This checkerboard exists on every map and it's solely there for use of the AI. Now, at 16 x 16, its pretty good for maps up until 20k (where the points are just over 1k apart), but after that, that grid is too coarse to be used for anything but air - and maybe naval - threats.

[Uveso]

Uveso likely knows this already

Hhhmmm. nope

Thank's for the Tip

[Uveso]

Naval pathing is now working flawless.

I recorded a test game with 2 lakes adressing the "Seton's Clutch" problem.
(naval units try to move over land to reach targets inside the opposite water area)

TKPlakepaths.png (435.45 KiB) Viewed 2470 times

Klick here for the video: (13 min)
https://youtu.be/djeGaH_7x0w

[Edit] The video does not show the original markers from the map. I modified some for testing.