So I decided to rearrange the processing order of navigation points during network mapping, putting 'already checked' navigation points on highest priority.
This means that nodes that have been queried during current mapping will be re-queried ASAP if another node is also connected to it.
This basically makes the route mapper expand 'circularly' instead of a 'amorphously' when calculating (sort of).
The timing (in QueryPerformanceCounter cycles) for MH-LostInTime were... interesting:
Old
Log: Execing routestest.txt
ScriptLog: Single mapping test: 161018
ScriptLog: Multi mapping test: 928420
ScriptLog: Single mapping test: 120287
ScriptLog: Multi mapping test: 890584
ScriptLog: Single mapping test: 159587
ScriptLog: Multi mapping test: 811491
ScriptLog: Single mapping test: 139318
ScriptLog: Multi mapping test: 986390
ScriptLog: Single mapping test: 144925
ScriptLog: Multi mapping test: 716283
ScriptLog: Single mapping test: 102488
ScriptLog: Multi mapping test: 598817
ScriptLog: Single mapping test: 157867
ScriptLog: Multi mapping test: 705820
ScriptLog: Single mapping test: 112214
ScriptLog: Multi mapping test: 728518
ScriptLog: Single mapping test: 172611
ScriptLog: Multi mapping test: 790090
ScriptLog: Single mapping test: 105768
ScriptLog: Multi mapping test: 509183
ScriptLog: Single mapping test: 75247
ScriptLog: Multi mapping test: 418101
ScriptLog: Single mapping test: 62302
ScriptLog: Multi mapping test: 358674
ScriptLog: Single mapping test: 59186
ScriptLog: Multi mapping test: 323364
ScriptLog: Single mapping test: 53303
ScriptLog: Multi mapping test: 292086
ScriptLog: Single mapping test: 45850
ScriptLog: Multi mapping test: 417325
ScriptLog: Single mapping test: 68217
ScriptLog: Multi mapping test: 381629
ScriptLog: Single mapping test: 63712
ScriptLog: Multi mapping test: 431441
ScriptLog: Single mapping test: 177232
ScriptLog: Multi mapping test: 812450
ScriptLog: Single mapping test: 160706
ScriptLog: Multi mapping test: 985483
ScriptLog: Single mapping test: 154586
ScriptLog: Multi mapping test: 843149
ScriptLog: Single mapping test: 110612
ScriptLog: Multi mapping test: 883181
ScriptLog: Single mapping test: 131078
ScriptLog: Multi mapping test: 873135
ScriptLog: Single mapping test: 161790
ScriptLog: Multi mapping test: 819132
ScriptLog: Single mapping test: 130813
ScriptLog: Multi mapping test: 862032
ScriptLog: Single mapping test: 173148
ScriptLog: Multi mapping test: 1053391
ScriptLog: Single mapping test: 174795
ScriptLog: Multi mapping test: 725566
ScriptLog: Single mapping test: 162255
ScriptLog: Multi mapping test: 802391
ScriptLog: Single mapping test: 158383
ScriptLog: Multi mapping test: 813634
ScriptLog: Single mapping test: 157039
ScriptLog: Multi mapping test: 823411
ScriptLog: Single mapping test: 179661
ScriptLog: Multi mapping test: 864736
ScriptLog: Single mapping test: 181915
ScriptLog: Multi mapping test: 1021477
ScriptLog: Single mapping test: 161002
ScriptLog: Multi mapping test: 937544
New
Log: Execing routestest.txt
ScriptLog: Single mapping test: 8597
ScriptLog: Multi mapping test: 34901
ScriptLog: Single mapping test: 9211
ScriptLog: Multi mapping test: 36720
ScriptLog: Single mapping test: 9114
ScriptLog: Multi mapping test: 68305
ScriptLog: Single mapping test: 11715
ScriptLog: Multi mapping test: 51036
ScriptLog: Single mapping test: 7242
ScriptLog: Multi mapping test: 34356
ScriptLog: Single mapping test: 9124
ScriptLog: Multi mapping test: 49828
ScriptLog: Single mapping test: 8597
ScriptLog: Multi mapping test: 55228
ScriptLog: Single mapping test: 10194
ScriptLog: Multi mapping test: 36119
ScriptLog: Single mapping test: 7697
ScriptLog: Multi mapping test: 37286
ScriptLog: Single mapping test: 8427
ScriptLog: Multi mapping test: 32922
ScriptLog: Single mapping test: 6451
ScriptLog: Multi mapping test: 31371
ScriptLog: Single mapping test: 5882
ScriptLog: Multi mapping test: 42007
ScriptLog: Single mapping test: 7071
ScriptLog: Multi mapping test: 50734
ScriptLog: Single mapping test: 10001
ScriptLog: Multi mapping test: 45633
ScriptLog: Single mapping test: 10489
ScriptLog: Multi mapping test: 57888
ScriptLog: Single mapping test: 7262
ScriptLog: Multi mapping test: 40072
ScriptLog: Single mapping test: 7601
ScriptLog: Multi mapping test: 46095
ScriptLog: Single mapping test: 6468
ScriptLog: Multi mapping test: 49586
ScriptLog: Single mapping test: 7463
ScriptLog: Multi mapping test: 45376
ScriptLog: Single mapping test: 8523
ScriptLog: Multi mapping test: 48329
ScriptLog: Single mapping test: 10170
ScriptLog: Multi mapping test: 45285
ScriptLog: Single mapping test: 7610
ScriptLog: Multi mapping test: 39979
ScriptLog: Single mapping test: 7220
ScriptLog: Multi mapping test: 34071
ScriptLog: Single mapping test: 5962
ScriptLog: Multi mapping test: 30814
ScriptLog: Single mapping test: 6775
ScriptLog: Multi mapping test: 25889
ScriptLog: Single mapping test: 4724
ScriptLog: Multi mapping test: 31055
ScriptLog: Single mapping test: 6272
ScriptLog: Multi mapping test: 33974
ScriptLog: Single mapping test: 4593
ScriptLog: Multi mapping test: 28936
ScriptLog: Single mapping test: 5969
ScriptLog: Multi mapping test: 21373
ScriptLog: Single mapping test: 3973
ScriptLog: Multi mapping test: 20929
ScriptLog: Single mapping test: 4400
ScriptLog: Multi mapping test: 21457
ScriptLog: Single mapping test: 6441
ScriptLog: Multi mapping test: 30632
Also ported the route cache builder to native code.
The path node limit for a linear route should be 15000.
Next challenge will be to write a unrealscript version of FindBestInventoryPath using this route mapper.
The goodies of this is that bots may be able to assess when items could be picked up along the route without altering the 'current' route, or even 'weighing' the route in a way that an item inbetween is picked up.
Let's brainstorm:
Bot needs to recover flag after respawning.
Stage one, select objective:
- Map entire network from
EFC's perspective.
- Build route between EFC and enemy flag.
- Select as
endpoint a path 'X' distance ahead of EFC.
Stage two, find nearest weapons:
- Re-map entire network from Bot's perspective (remap is less expensive, Cost not assigned to paths because already assigned during EFC mapping)
- Measure [VisitedWeight - WeaponWeight*Constant] to InventorySpot paths marking weapons.
- Cache a list of nearest 8 [Weapon+Weight] based on this.
Stage three, get best weapon+route to EFC's
endpoint.
- Re-map entire network from each weapon and measure endpoint's VisitedWeight.
- Sum in each case: WeaponWeight + endpoint's VisitedWeight from that weapon.
- Pick weapon where said sum is the lowest.
Additionally I could make it so that Botz's translocation chain directly targets items if the next path is an InventorySpot actor holding an item, so bot can pick up the item during translocation chain.
I was thinking with making a 'reverse' MapRoute function where the weight of all paths INTO a node is calculated if each of these paths were the starting point, that'll simplify stage three tremendously.
It'll be bugged because UpstreamPaths list in NavigationPoint can only hold 16 connections, and it's possible to have more incoming paths than just 16.
In cases like Assault/MH it could be possible to direct a bot to select a few items as his 'kit' before attacking, by already reviewing each of the nearby items in the path network, instead of randomly telling him to find inventory in the middle of attacking.
Network mapping makes coding Bot ai a lot more fun.