A* Algorithm

Recommended Posts

Hi there, folks!

Here's Luk, one of the developers of the RotU-Revolution mod. It has been quiet for a long time now and I've just recently heard about this project and its possibilities.

Since I have no experience in C++ (or its C-variants) I'd like to ask for help.

As some of you might know, Zombie mods usually use pathfinding algorithms, namely the A* (A-Star) algorithm which (I believe) shipped with Petzbots. You can find the .gsc implementation here.

There are a couple C++ examples of the named algorithm publicly available on the internet and I'd love if someone could make them usable as a plugin. Another function to unload/reload the waypoints would be nice to have, too, for example for (future?) dynamic maps.

I hope there's someone out there who'd like to help. If you have any further questions, hit me up.


Share this post

Link to post
Share on other sites

we have had some great discussions on getting bot support into cod4x and including pathfinding would be a logical step for me.

also note that cod4x has a ton of additional bot specific gsc funs

first of all it is to consider why you want to port pathfinding from GSC to C. is the runtime cost of A* so significant against the rest of the code? 
if it is i'm not sure if using A* is even a smart choice. given that the waypoint graph is static ( i.e. doesnt change ever ) we can precompute the possible paths with an all-pair-shortest path algorithm ( floyd-warshal )

where can i take a look at those waypoint files?

Share this post

Link to post
Share on other sites

We haven't run any in-depth performance tests on pathfinding, but we highly suspect that pathfinding takes a big part of the computational resources for the specific server thread. It also sometimes happens that the server bugs out with a "killing infinite loop" message and - with our limited knowledge about the engine - we suspect that too many pathfinding calculations happen within one frame, thus making the server skip 2.5 seconds (iirc) or 50 frames and causing many players to die instantly. (On a sidenode: Can 1.8 tell the function that might be causing an infinite loop detection? We've triple-checked all for and while functions and couldn't find a cause yet, thus suspecting the pathfinding itself)

You can find (some of) the waypoints in here. The files have the suffix _waypoints:

They also come as compiled .csv files inside the fastfiles of maps and are loaded with loadWaypoints().

Share this post

Link to post
Share on other sites

Oh, that might finally solve that problem. I guess I'll have to get used to all those new features. Thanks for that piece of information!

Share this post

Link to post
Share on other sites

i was never able to get this line() function to work, do you know what i have to enable for that to work?

i've found the script to load waypoints from csv files, but where is the script that writes the csv? also could you send me some csv files? i know you said they are somewhere in the fastfiles, but you can get your hands faster on them than me probably :)

Share this post

Link to post
Share on other sites

If I remember correctly, you must start a local session with "+set developer 1 +set developer_script 1 +set zom_developer 1" to see the lines. (Might require Rotu 2.2.2 to use, but the structure of those waypoints is the same across different mod variants)

I'm afraid I don't have a waypoint.csv, so I've taken an example from

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

id,x y z, child1 child2...

EDIT: Awesome! :)

Edited by Luk

Share this post

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.