GregHib
Bot navigation
Search for target first by tags #39 and then find the shortest route to that target, or search dijkstras to find the nearest applicable area?
Abstract nagivation map made up of waypoints within distance (15 or several chunks?) of each other, stored by chunk. Ai then stores waypoints and adds tiles as influence for next decision.
Waypoints
- Unidirectional so a bot can add dynamic options based on inventory etc.. (glory to tele to edge etc..)
- Weighted/contain requirements the bot must meet or things influenced by (prioritise musician routes)
- Pre-calculate walkable tiles vs run 30x30 bounded flood fill after each movement?
Consider
Static teleports
- Doors
- Gates
- Shortcuts
- Gnome glider
- Fairy ring
- Spirit tree
- Flying carpets
- Levers
- Baloons
- Gnome copters
Dynamic teleports
- Jewlery
- Spellbook with runes
- Teleport tabs
Validation
If waypoint map is being manually built, need a way to verify that paths are valid and a bot won't get stuck
Waypoints
- Unidirectional so a bot can add dynamic options based on inventory etc.. (glory to tele to edge etc..)
- Weighted/contain requirements the bot must meet or things influenced by (prioritise musician routes)
- Pre-calculate walkable tiles vs run 30x30 bounded flood fill after each movement?
What do items 2-3 mean?
2 refers to
- cost of traversing a graph
Edge. For now this is simply distance - Requirements to traverse a graph
Edge. E.g A boat requires a money, walking does not
3 is the issue of finding the nearest graph node to a player, options are:
- Flood fill the surrounding area until one is found: current, however costly to do an extra bfs call every time a player moves
- Flood fill the entire map on startup to calculate the closest node for any given tile: significant startup delay and ram overhead
- Store a copy of the graph in a spatial structure that supports nearest-neighbour search: 1nn could be costly (needs benchmarking in realistic scenario, aka wait for more bots), keeping both graphs in sync is complex and have to weigh the costs/benefits of different structures, their update complexity and ram usage.
Ticket itself is half complete, static teleports are working, dynamic works in theory but has nothing implmented and there's no validation that the manually built graph is correct.