When developing Bots what do you used, ie whats in the code?

[Lethal]

What I mean by this Is that I am interested how bots function.
Today I learned about Graphs. Mathematical graphs of course, not simple bar graphs and such, but graphs made from vertices and edges.
And during the lecture it occured to me is this what is used to help bots navigate?

[Rick]

what is used to help bots navigate?

That could be anything
If the bots are using waypoints they just aim and walk to that waypoint and will walk to other, connected, waypoints to reach his goal.
They could use 'TraceLine' navigation, a TraceLine is used to determine if there is some obstacle between 2 points, that way a bot can 'see' if there are any obstacles and try to avoid them. They(tracelines) can also be used to determine which point is the 'most reachable'(furthest obstacle seen from bot) and go that place, that way they can walk in hallways and such.
And finally you could use mapdata, basicly what I do is putting waypoints on all valid(reachable and such) cube's in a map(Cube has a simple 2d grid for map data). So in my case its more waypoint navigation without the need that someone should create it by their self.

I guess PMB can tell more about his navmesh stuff

[Lethal]

Thanks,
Wouldn't using graphs that use edges be useful since you could add information to waypoints and their connections by weighted digraphs (I think that is the right term) and help bots find the quickest routes to their destination.
I can see how tracline would help but surely that would increase cpu load since the waypoints would have to be spaced quite closely?

I don't know if this would work but this is what I am sort of thinking.

[@$3.1415rin]

yes, that waypoint stuff is an application of the graph theory in mathematics. most older bots used the floyd warshall algorithm for determining the shortest path, an algorithm, which allows offline calculations and fast lookup. unfortunately it's also pretty static. to include dynamic costs A*, D*, or ( realbot once used ) BFS are used.

gotta take a look at the lectures here and see what kind of stuff is covered there. although that might be a bit tooo theoretical for usage in bots if that lecture is done by the pure mathematicians

[Pierre-Marie Baty]

An article about pathfinding had been started in the wiki already.. I'm yet to finish it... but yes, basically, vertex == waypoint, edge == path, weightened digraphs == cost/heuristic traversal (such as A*). You are right on all the line.

[Lethal]

how do you store the information regarding waypoints?
I learned that information concerning connections in the graph are stored using matrices, is this used, or something related in programming?
And could bots use algorithms to navigate, in the method I have been quering about?

[@$3.1415rin]

in the bots we dont usually use matrices, since they'd be pretty big ( let's say, we want to have at maximum 8192 waypoints, that'd be 8192*8192*2bit = 16 mbyte. resizing such arrays might be a bad idea, therefore a maximum size array here. and using triangular matrices for the connections doesnt sound like a good idea, since we might wanna have paths only to one direction. hm, 2 triangular matrices would work. anyway, not much advantages )
for each vertex there is often a list of indices to which the waypoint is connected. since most waypoint graphs are not very dense connected, this saves a lot of space.

for used algoirthms, take a look at the wiki ...

[stefanhendriks]

like asp said.

Basicly:

waypoint
{
vector location;
int connections[max_connections];
}

where a connection is simply an index referring to a waypoint it can reach.

For floyd algo's you do need a static matrice. But you will probably only have 500 waypoints then. 500x500x2bits = 250000*2 = 500000 bits... / 8 = 62500 bytes.

For algorithms. You could take a look at existing algo's, but along with that i suggest you try to think as a path finder as well. Gives a bit mor einsight how things are 'working'. Perhaps you get some insight and show us the lightned path of unwaypointed navigation...

[Pierre-Marie Baty]

unwaypointed navigation is easy...
it's unwaypointed pathfinding which isn't

[stefanhendriks]

hehehe yeah Well ofcourse with unwaypointed navigation we do not mean "walk to wall, bump, turn 90 degrees to random direction and so forth"...