The Dijkstra Project
Posted: Sat Apr 12, 2014 1:17 am
[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
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
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?
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?
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
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");
};
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]; //?
};
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?