The Dijkstra Project

Discuss Artificial Intelligence and Bot programming.
OneManClan
Posts: 247
Joined: Sat Feb 28, 2009 2:38 pm
Contact:

The Dijkstra Project

Post by OneManClan »

[Disclaimer: I haven't even *tried* to compile the code presented here. I'm only showing it to get feedback on the overall 'method'/concepts. Newbies: This is more 'adventures of a beginner' than a 'tutorial', be warned: there's a good chance something I say will be simply untrue, and code I present will be sub-optimal, if not plain old WRONG! :) ]

OBJECTIVE
To make it so bots can get from positionA to positionB in a map, without getting stuck on corners, under stairs, etc. ie Navigation.

BACKGROUND INFO
What initially started as 'minor adjustments' to the CustomTF bot 'Grunty' has become a 'rewrite', with the latest desire being to stop from getting stuck on corners. This has resulted in an obsession (and investigation) into waypoints, pathfinding, A* and Dijkstras algorithm, hierarchical pathfinding, Catmull Rom optimisations, etc. I've been looking at Frikbot and Havocbot code, and have a (very) rough idea of what's going in. I'm not sure whether the way forward is to keep reading these highly regarded implementations (ie until I understand them enough to be able to extract the pathfinding concepts from all the AI), or jump in and just write my own basic system. I'll keep doing the former, but in the meantime, I've come up with the following VERY ROUGH implementation.

THE METHOD
Both Spike and LordHavoc (thanks guys!) have given the thumbs up for Dijkstra's algorithm, and .. they can't BOTH be wrong... can they? :)

(Proposed) Version 1.0
STEP 1: MAKE THE WAYPOINTS
So, I've gone through 2fort5r, and manually outputted vectors(into a txt file), placed in 'points of visibility' positions, expressing a path through the map, away from walls (of course), navigating the ramps in the ramp room. The only possible complexities are 'one way' paths from the Grid, and the snipers deck, where a bot can jump down, but not back up, but let's leave that aside for now.


STEP 2: LOAD THE WAYPOINTS INTO AN ARRAY

Code: Select all

#define MAX_NODES 50 
entity node[MAX_NODES];


// opens the mapname_nodes.txt file, which contains about 40 vectors
// all within sight of at least 1 other vector
// spawns the node entities and positions them
// returns the number of elements in the array
float () WaypointLoad =
{

    local float  file, i, temp;
    local string str;


       // mapname is a global
       str = strcat(mapname,"_nodes.txt");
       
       file = fopen(str, FILE_READ);
       
       if(file < 0)
          {
             dprint("Problem opening ");
             dprint(str);
             dprint("\n");
             return;
          }
       
       
       for( i = 0; str; i++)
          {
             str = fgets(file);
             
             if (str == "") continue;
             
             node[i] = spawn(); // spawn it
             setorigin(node[i].origin, stov(str)); // position it
                          
             
             dprint("Positioning node ");
             dprint(ftos(i));
             dprint(" at: ");
             dprint(vtos(node[i].origin));
             dprint("\n");
       
          }
       
       fclose(file);
       temp = i;
// remove the array elements not needed - not sure this is correct
       for ( ; i< MAX_NODES; ++i)
            {
             remove (node[i])
            }
                                   
       
       // return the number of elements in the array
       return temp;

};
num_of_nodes = WaypointLoad(); // the array is set, and we know how many there are

STEP 3: MAKE THE GRAPH AND WEIGHT THE NODES
Figure out which nodes are visible to each other, calculate distances between them, and store the result

Code: Select all

// This does the weightings
// finds each node that can see anither node and stores the distance between them
// maybe this should be done previously and loaded to file
void () WeighTheNodes =
{

local entity e[num_of_nodes], comparison_e;

e[i] = findchain(classname, "node"); // get first node
    for (i=0; i < num_of_nodes; i++) // search through all the nodes
        {
            for (j=0; j<num_of_nodes; j++) 
                {
            comparison_e = findchain(classname, "node"); // get a comparison node
            if(e[i] == comparison_e) continue; // if its the same one skip
            
            if(isvisible(e[i], comparison_e) // the comparison node can see the current
              {
                e[i].target[j] = comparison_e; // add it to position j of  e's target array
                e[i].distance[j] = vlen (e[i], comparison_e); // and store how far it is from e (weight)
              }

              comparison_e = comparison_e.chain; // get the next thing to comopare with
                }

        }
    e[i] = findchain(classname, "node");
};


STEP 4: RUN THE DIJKSTRA ALRORITHM
Ok this is the tough part, not sure if it's too ambitious to try to do it all in one function; anyway, we have a series of 'for' loops, do the Dijkstra algorithm, and store the results using a FIFO...no, it doesn't add the cumulative weightings(yet), and I haven't figured out the FIFO bit yet (ie storing and accessing the results), this is REALLY ROUGH, ok? :)

Code: Select all

result[0] (entity start_node, entity Endnode) Dijkstra =
{
  local entity e;

    start_node.processed = 1;
    num_of_processed = 1;

    PutOnStack(start_node);

    while (num_of_processed < num_of_nodes)
    {

      if(NumberOnStack() == 1) // if this is the first runthrough..
        e=start_node;  // start with the start_node
        else            
      e = find(world, processed, 0); 
      for (i=1; e; i++) 
      {

        if(e )
        sample = find(world, is_connected_to, e); // find all the nodes whoch connect to this one
        
        for (k = 1; sample; k++)
          {

            if(best_node_so_far.distance == 0) // 1st iteration
              best_node_so_far= sample;
            else
              if (best_node_so_far.distance > sample.distance) // sample node is closer
                  {
                    best_node_so_far= sample; // it becomes THE ONE
                    best_node_so_far.processed = 1; // mark the node as processed
                    best_node_so_far.distance = best_node_so_far.distance + e.distance;
                    PutOnStack(best_node_so_far);
                    num_of_processed ++;
                  }

            sample = find(sample, is_connected_to, e); // this entity         
          }

          e = find(e, processed, 0); // for each node that has not already been processed
      }

    }

// end up returning some_newly_created_array[0]; //?
};
Ok, well that's as far as I've gotten, still obviously a wip, mainly posting this to get feedback on the validity of the general concept, especially the loop system in Dijkstra(). I'm still not sure whether to use arrays (havocbot doesn't), or even a C type struct data type (which fteqcc allows)...

NEXT STEP: Learn more about 'priority queues'. Much of the reading emphasised to use this instead of a FIFO. Also, (obviously) need to finish the algorithm itself, and figure out how to return the finished path .. create a linked list, and send the 1st element(?) etc

Your feedback please... am I on the right track, or not?
Last edited by OneManClan on Sun Apr 13, 2014 4:40 pm, edited 1 time in total.
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: The Dijkstra Project

Post by Spike »

find finds strings. don't use it for floats or ents. that way lies madness (or instability).
findchain finds a chain of entities. if you call it multiple times within a loop, or recursively, then you lose.
field arrays are best kept small. your code will need 160 new fields. you should probably prioritise them.
OneManClan
Posts: 247
Joined: Sat Feb 28, 2009 2:38 pm
Contact:

Re: The Dijkstra Project

Post by OneManClan »

Spike wrote:find finds strings. don't use it for floats or ents. that way lies madness (or instability).
Ah.. ok, thanks.
Spike wrote:findchain finds a chain of entities. if you call it multiple times within a loop, or recursively, then you lose.
Ahhh.. so my 'super function' with multiple nested loops wont work? Hm.. what about 'find'...is this ok?:

Code: Select all

entity1 = find(world, foo, "1");
      for (i=1; entity1; i++)
      {
        entity2 = find(world, foo, "1");
        for (k = 1; entity2; k++)
          {
            entity2 = find(world, foo, "1");
          }
          entity1 = find(e, foo , "1");
      }
Spike wrote:field arrays are best kept small. your code will need 160 new fields. you should probably prioritise them.
Hmmm ... I assume you're referring to this bit:

Code: Select all

if(isvisible(e[i], comparison_e) // if the comparison node can see the current
              {
                e[i].target[j] = comparison_e; // add it to position j of  e's target array
                e[i].distance[j] = vlen (e[i], comparison_e); // and store how far it is from e (weight)
              }
Each node should only see 3-4 other nodes, so (in this implementation) we're talking an extra 4 entity (node) fields, and 4 floats (distance). The array of all (max) 50 nodes are a global array. What am I missing?

Also, by 'prioritise' are you referring to the use of a priority queue (which I'm not yet familiar with), or some other method/concept?
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: The Dijkstra Project

Post by Spike »

find is slow. slow slow slow. it has to do string comparisons for every single entity on the map. it does not scale.
findfloat is better, but still has to check lots of entities.
you don't prioritise. in fact, if your array is anything less than 'num_of_nodes' then I assume you'll write your array out of bounds.
I should also point out that local arrays are not normally supported (#pragma target fte for that). dynamically sized arrays are not supported either (although I could theoretically implement that, there's no support right now). have fun.
ratbert
Posts: 37
Joined: Thu Nov 19, 2009 3:47 pm

Re: The Dijkstra Project

Post by ratbert »

OMC couple things

1) Take a look at the last release of CustomTF coop that gizmo maintained. I sent him some code changes that would address some issues with grunties getting stuck and I know he had some things he did to the gruntie bot code to improve it.

2) I know way back there were a couple mods our there that one was TFBot for regular team fortress and another CTFBot for Capture The Flag mod. Remember TFBot one was not bad other CTFBot was pretty good at play CTF mod itself. Course that way back in late 1990's - early 2000's when I last played them. Source code is out there somewhere on the net.
OneManClan
Posts: 247
Joined: Sat Feb 28, 2009 2:38 pm
Contact:

Re: The Dijkstra Project

Post by OneManClan »

ratbert wrote: 1) Take a look at the last release of CustomTF coop that gizmo maintained. I sent him some code changes that would address some issues with grunties getting stuck and I know he had some things he did to the gruntie bot code to improve it.
Hey Ratbert! Yes, thegizmo added some finesse to Grunt movement ( bot moves back when it's blocking the owner, fixed static mode). Apart from a waypoint system however, is there any way to stop a Grunt from (eg) getting stuck on the steps/ramps at the entrance of 2fort?:
https://www.flickr.com/photos/60268498@N06/13839285304
ratbert wrote:2) I know way back there were a couple mods our there that one was TFBot for regular team fortress and another CTFBot for Capture The Flag mod. Remember TFBot one was not bad other CTFBot was pretty good at play CTF mod itself. Course that way back in late 1990's - early 2000's when I last played them. Source code is out there somewhere on the net.
Wow, I always thought the TFbot might be an urban myth, based on this thread, an abandoned wip that no-one actually got to play but yea, there you go.. I'd love to see the source.

Are you using any pathfinding code for your (amazing) RatBert co-op?
OneManClan
Posts: 247
Joined: Sat Feb 28, 2009 2:38 pm
Contact:

Re: The Dijkstra Project

Post by OneManClan »

Spike wrote:... dynamically sized arrays are not supported either (although I could theoretically implement that, there's no support right now). have fun.
Well .. is it accurate to say that declaring an entity makes space for an entity pointer, and until it's spawned it doesn't take up much memory? eg:

Code: Select all

//global
#define MAX_NODES 40 
entity node[MAX_NODES]; // IIUC these are (at this stage) 50 entity 'pointers', ie they don't take up (much) space

void() Func_1 =
{
// spawn the first 20
       for( i = 0; i < 20; i++)
          {
             node[i] = spawn(); // IIUC *this* is where the memory gets reserved for an actual entity
          }
       
// IIUC this bit is ineffectual: 
       for ( ; i< MAX_NODES; ++i)
            {
             remove (node[i]); // This assigns the second 20 nodes to 'world' - to which they were already 'pointing to'!
            }

// OTOH this *does* actually free memory
       for ( i=0; i< 20; i++)
            {
             remove (node[i]); //????
            }
                 
}     
 
Q: Is the above accurate?
ratbert
Posts: 37
Joined: Thu Nov 19, 2009 3:47 pm

Re: The Dijkstra Project

Post by ratbert »

OMC at one point I had Frik Bots / Custom TF bots code combined into one thing. Using Frik bot waypoint/other main things and customf tf bots weapons/skins. Basically it was setup that when CustomTF mode ( i.e. team fortress and/or coop) they would use that CustomTF logic and when in deathmatch mode they using Frik Bot logic. One of those things that worked just find except for a couple things being. Deathmatch mode a bot having same weapons as players meant almost instant death way weapons were geared for coop play. Other was that having Frik Bot code in the mode meant less monsters / things I could add. So kinda abandoned idea and just geared the mod directly for coop play. I do not know even if I have that project still around in - I can look around for it.

I know I got some of the TF Bot source code (decompiled stuff) that could help you and CTF bot code to. Need to find them in archive of stuff I keep.

Other thing is look at the very last release source that Gizmo released on CustomTF coop code and other source mod CustomTF For The People (or something code to that name) that is basically a split off that the created from Gizmo source code with additional things for CustomTF. I know all that stuff is up at SourceForge to look at.

When I find the source code is there a way you want me to get to you?

Did you check with Spirit who runs Quaddicted.com - He may have some source code. I know he collects anything and everything quake related.

OneManClan wrote:
ratbert wrote: 1) Take a look at the last release of CustomTF coop that gizmo maintained. I sent him some code changes that would address some issues with grunties getting stuck and I know he had some things he did to the gruntie bot code to improve it.
Hey Ratbert! Yes, thegizmo added some finesse to Grunt movement ( bot moves back when it's blocking the owner, fixed static mode). Apart from a waypoint system however, is there any way to stop a Grunt from (eg) getting stuck on the steps/ramps at the entrance of 2fort?:
https://www.flickr.com/photos/60268498@N06/13839285304
ratbert wrote:2) I know way back there were a couple mods our there that one was TFBot for regular team fortress and another CTFBot for Capture The Flag mod. Remember TFBot one was not bad other CTFBot was pretty good at play CTF mod itself. Course that way back in late 1990's - early 2000's when I last played them. Source code is out there somewhere on the net.
Wow, I always thought the TFbot might be an urban myth, based on this thread, an abandoned wip that no-one actually got to play but yea, there you go.. I'd love to see the source.

Are you using any pathfinding code for your (amazing) RatBert co-op?
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: The Dijkstra Project

Post by jitspoe »

I'm not sure if this will be of any help, but I'm also at the beginnings of AI programming and have some source (in a rough state) up here:

http://paintball2.cvs.sourceforge.net/v ... all2/bots/

It's for Quake2, but kind of separated from the game code (in its own lib). I think you could make use of the astar code -- at least for reference. I used JABot and some various tutorials for reference. JABot seemed a little over-engineered, so this is stripped down a little.
c0burn
Posts: 208
Joined: Fri Nov 05, 2004 12:48 pm
Location: Liverpool, England
Contact:

Re: The Dijkstra Project

Post by c0burn »

Cobalt
Posts: 445
Joined: Wed Jun 10, 2009 2:58 am
Location: New England, USA
Contact:

Re: The Dijkstra Project

Post by Cobalt »

I have been modifying the original ctfbot+ code for years to try and improve the botai. My mod is called Tekbotctf+

Nav is THE biggest issue for sure. The CTFBOTS pretty mch use findradius to see what items are in the area, then if visible, are "flung" to them in a straight line. Yea, they can hit corners, but with older Quake they are movetype_step, and I believe it helps them when going around the corners, also if I recall this movetype wont fall off a ledge, rather it will follow along the edge(s) of such an area.

Newer bots like Frik, are nearly 100% cloning actual human players, and the walk movetype will now make them stick on corners as well as fall off ledges. Frikbot pretty much does a decent job of stopping them from falling with tests first.

One thing I am experimenting / trying is using trace_plane_normal on the bot , embedded into a new.touch for the bot. Whenever a .touch is called most engines will set trace_plane_normal that same frame so that you can refer to it in the ents .touch function. Compare the values in that to see if its against a wall , and I guess check if velocity is under a certain min value, and its stuck. Spike had told me a while ago that its not the best way to get trace_plane_normal like that, and I agree the traceline would be better, but so far in my mod is has been ok, and I use DP.

Not sure how good your code is Coburn....hope you put up another demo showing it in use maybe.
OneManClan
Posts: 247
Joined: Sat Feb 28, 2009 2:38 pm
Contact:

Re: The Dijkstra Project

Post by OneManClan »

Update:

I've put aside my 'newbie guesswork' code and focused on studying c0burn's 'actually working' implementation. One thing I'm confused about is how to make it so the player can call his bot from any position in the map, and have the bot find him, and end up standing right next to him, not the waypoint. My original idea was:

Code: Select all

// runs once a second
if (the bot has a clear line of sight to owner) walk towards him;
if (bot gets stuck) use Dijkstra to get to the last waypoint the owner touched;
if (bot is at the last waypoint the owner touched) walk directly to the owner;
There are two problems here:
1. Players not always touching waypoints. IIUC most AI requires the player to touch/trigger a waypoint for it to become the 'target waypoint' for the bot to use. But many maps have wide doorways, and open spaces where a player can move around without triggering the waypoint. What then? Use bigger sized waypoints to reduce the chance that a player will walk past without triggering it? But then how does this affect the smaller areas/thin ramps etc? Have different sized waypoints?

2. Once the bot reaches the 'last waypoint the player touched', and we want the bot to walk towards the player himself, what happens when a bot CAN see him, but CAN'T get to his side? eg Here we have two waypoints (the ankhs), both can see the player, waypointA is closer, AND it is the last one the player touched, BUT a bot standing at waypointA cannot reach the players position from it (the red path):
Image
Normally, waypointA would be a valid place to attack from, but we want this friendly bot to use waypointB, so it can follow the (unobstructed) green path, directly to the owner... so how do we tell the bot to use it? I suppose you could use more waypoints - but this seems.. sloppy.. and increases the number of nodes that need processing.

I realise most bots are designed to attack as soon as they get an opportunity.. is this 'come here, friendly bot' complex, or am I missing something obvious?
Last edited by OneManClan on Thu Sep 04, 2014 8:59 am, edited 9 times in total.
drm_wayne
Posts: 232
Joined: Sat Feb 11, 2012 5:47 pm

Re: The Dijkstra Project

Post by drm_wayne »

Is c0burn's source avaiable?
I made an custom bot back in the days with waypoint navigation, and if the bot sees the player he will start moving and attacking the player.
Also i added the "tracker system" from aicafe, so if the player walks around a corner / thru a teleporter the bot / enemy will chase you.

https://www.quaddicted.com/webarchive/m ... m/news.htm
OneManClan
Posts: 247
Joined: Sat Feb 28, 2009 2:38 pm
Contact:

Re: The Dijkstra Project

Post by OneManClan »

drm_wayne wrote:Is c0burn's source avaiable?
I made an custom bot back in the days with waypoint navigation, and if the bot sees the player he will start moving and attacking the player.
Also i added the "tracker system" from aicafe, so if the player walks around a corner / thru a teleporter the bot / enemy will chase you.

https://www.quaddicted.com/webarchive/m ... m/news.htm
Hi drm_wayne,

Thanks for your response. c0burns ai code is still in development, and as you can see in his (wip) vid, the monsters don't go to the player himself, but to the 'last waypoint the player touched', and staying there till he touches another. IIUC Frikbot also uses waypoints until the enemy is visible, and then attacks .. otoh.. there must be places where bots can see their enemy but must backtrack to get to them.. hmm .. I'll have another look . [Edit: and also study how Frikbot does melee attacks, which presumably require that the bot move towards its enemy, presumably without getting stuck]

Thanks for the "tracker system" info, GREAT tip on how to make bots follow people into teleporters!
I imagine the solution to all this is to make the goalentity.origin (in this case a friendly owner not an enemy) be the final waypoint. So the question is: "how can we make WaypointB (as per my screenshot/diagram) realise that it is the valid/accesible waypoint"? Or maybe the question is "how to make WaypointA realise that even though it is closer to the target than waypointB, a bot cant get through the obstacle"..(?)
[EDIT: I'm looking into the tracebox() builtin, which might be able to let a waypoint know if a bot at that waypoint can reach a target/goalentity
tracebox(waypoint.origin, target.origin, size of bot MIN, size of bot MAX, #TL_BSP_ONLY, waypoint); // something like that..]
Last edited by OneManClan on Thu Sep 04, 2014 4:19 am, edited 1 time in total.
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: The Dijkstra Project

Post by jitspoe »

You might consider switching to A*. Dijkstra explores all possible waypoints and can be expensive. A* is a bit smarter, so it can be a big performance gain if you have a lot of points.

I have some code here (that I heavily referenced ACEBot source for): http://paintball2.cvs.sourceforge.net/v ... all2/bots/

Your data structures will likely be different, but maybe the logic will be a worthwhile reference.
Post Reply