bot navigation

[D4edalus]

path finding plugin for bots. https://cod4x.me/index.php?/forums/topic/1362-a-algorithm/#comment-6163

csv file format exists

prerequisites:

• code to read csv files: https://github.com/doctorluk/Reign-of-the-Undead-Revolution-Scripts/blob/8f43cb378e61770dfd2edd02ab5760892f4e9bbb/scripts/include/waypoints.gsc#L33

• csv file examples: see below

• gsc code to write csv files: TODO

functions to implement:

• loadWaypointsFromCSV(filename)
• findPath(vec3 start, vec3 end) : returns array of waypoint positions

notes:

• finding the nearest waypoint to any position should probably use a k/d tree as the vertex set is a few hundred nodes in size
• pathfinding can use a-star or probably even better precomputed path matrices from floyd warshal. a-star is more flexible as it allows us to add and remove nodes on the fly.

[D4edalus]

waypoint csv example

1,1502.11 2679.39 16.125,1 39
2,1090.22 2688.64 16.125,0 2
3,1100.05 2999.97 16.125,1 3
4,1818.22 2959.68 16.125,2 4
5,1822.3 2482.07 16.125,3 5 24 23
6,1828.94 1692.12 16.125,4 25 23 30 31
7,1834.58 748.283 16.125,7 31
8,1574.86 752.801 16.125,6 8 29 30 33
9,1576.93 463.339 16.125,7 9 33
10,1579.85 109.44 16.125,8 10 12 33
11,1857.61 99.621 16.125,9 11
12,1852.39 530.199 16.125,10
13,1147.18 129.612 16.125,9 13 33
14,767.694 147.996 16.125,12 14 32 33
15,247.128 183.629 16.125,13 15 32
16,268.407 701.003 16.125,14 16 32
17,286.642 1175.5 16.125,15 17 27
18,289.172 1442.1 16.125,16 18 19 26 27
19,66.2321 1468.08 16.125,17
20,275.74 1869.32 16.125,17 20 26
21,261.71 2249.49 16.125,19 21
22,501.735 2244.24 16.125,20 22 26 35
23,843.88 2238.94 16.125,21 23 26 25
24,1239.39 2232.17 16.125,22 24 25 5 4
25,1253.17 2513.85 16.125,23 4```

[leiizko]

• gsc code to write csv files:

This can be easily done using filesystem functions - example - Simply save waypoints to array, each array element having one waypoint. Each line is then one array element. Another example of simple waypoint editor that uses this: editor

• code to read csv files:

This could also be done (I also believe it is cheaper than constant table lookups) with filesystem - example. Each line is saved to single array element, then you can do whatever with read text. example of reading

Edit: Better example of reading added as it involves vectors.

[AlexanderCurl]

Awesome @leiizko. Up!

[T-Maxxx]

I'm still thinking about implementing AI into server code with all path-/enemyfinding routines. And about mod that will help to easily create waypoints set for each map. @IceNinjaman have added Q3's botlib into repo some time ago. It can be used as reference and it uses same usercmd structure for bots' commands.

[IceNinjaman]

Well main reason I added it was that I planned to get the "Area Awareness System" of Q3 working... However a lot of engine call backs are needed to get the botlib running at all. However all I got done so far is the Z_FreeTagMemory() function.

[D4edalus]

i dont know if theres better info on what it is and what it does .. but thats what i found from a quick search http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Waveren_Jean-Paul_van/thesis.pdf Page 34 ( in the pdfs page numbering )

ftp://ftp.idsoftware.com/idstuff/quake3/tools/ -> a3abot*

[D4edalus]

not sure what this is, but looks interesting. https://rsebots.blogspot.co.at/2017/03/good-news.html?showComment=1493804839389#c6521079130465280534

[ineedbots]

I reworked the a* path finding algorithm in my Bot Warfare mod for WaW, CoD4 and MW2.

This modification of a* allows me to get the not only the next waypoint needed to reach the destination but even the next waypoint after that one to have the bots look at (like looking around a corner, etc). It is optimized as I found the Pezbot's implementation to use unnecessary spawnStuct()'s that were getting overwritten as soon as they were created as well as unnecessary linear searches as I use a dictionary lookup instead.

Here is the implementation: https://pastebin.com/j9y1K0Au

[T-Maxxx]

As I said: I'm trying to make highly configurable mod where all you have to do is moving around and collecting orbs. Based on collected orbs it will produce file with all possible paths set (N, W, S, E, NE, NW, SE, SW + custom points support). Moving up\down by ladders will be supported by few layers of orbs like that.

[ineedbots]

I have implemented a k-d tree for NNS. As well I have reworked a* to use a heap for the priority queue and sets for quick look.

Here's what I did: https://pastebin.com/WeQ6S9e0

[doctorluk]

Thanks @ineedbots for the link. Can this be used in place of pezbots' A* algorithm? Are there differences in performance?

[ineedbots]

It can replace the pezbot's a*.

The difference in performance is very good. The NNS uses on average log_2(waypoints.size)*2 recursive calls, sometimes spiking to about half of waypoints.size. This is much better than the linear search for nearest neighbor which is always waypoints.size.

The use of a heap for the priority queue instead of a list is a massive performance boost. Popping the node with the largest f is constant time. Whereas pezbot's implementation for getting the largest node is always the size of the queue. Deletion from the heap is log_2(size of queue). Pezbot's is the size of the queue again. Insertion is the only place where pezbot's implementation is better, it is constant, whereas a heap will be log_2(size of queue) (which isn't bad).

Pezbot uses a closed list to store the nodes that have been looked at and a open list for the priority queue. My implementation uses a heap for the priority queue as stated before, but as well as two sets (hash dictionaries), one for nodes I've looked at and one more for nodes in the priority queue. Using a list to check if an item exists in it is dependent on the amount of items in the list. But using a set is on average constant time.

[doctorluk]

Thank you very much for the detailed explanation.

We would love to try and use this in our mod. Are we allowed to use your code and are there any conditions that need to be met when doing so?

[ineedbots]

Just give credit with what you use and all is good.

[AlexanderCurl]

Awesome job.

[doctorluk]

@ineedbots I've been trying to implement your solution but I'm stuck with lines 299 and 300. The variable "level.waypointsKDTree" is never initialized in your script. Is that on purpose or is something missing?

[ineedbots]

You need to initallize the tree, right after you initalize the waypoints do this:

for(i = 0; i < level.waypointCount; i++) { level.waypoints[i].index = i; }

level.waypointsKDTree = WaypointsToKDTree();

[ineedbots]

Heres my implementation of bots in GSC

https://cod4x.me/index.php?/forums/topic/3116-release-bot-warfare/

[leiizko]

I believe this pretty much solves the issue. https://github.com/leiizko/cod4x_lua_plugin/tree/master/LuaScripts/Rotu-R

And as it is written in Lua it can be very easily modified to fit any mod, without much coding knowledge.

[doctorluk]

Much appreciated, thank you!