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

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?

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

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 :)

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

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.

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

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 :)

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

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.

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

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?

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

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 ...

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

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... ;)

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

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

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

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

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

bleh, have you forgotten the RACC preview ? its navigation was better than those of MANY waypointed bots ! to speak like that you mustn't even have tried it I bet :)

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

i still see that bsp approach as some way waypointed ... well, again, the waypoints are named surfaces and they have some sort of relation to each other, otherwise you couldnt run A* on it. so to me that falls into the category 'waypointed' and that's maybe the best way to go.

but we had this already in amsterdam :D

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

@ pmb, i was speaking in general ;) Not about bots specific.

I did not try your preview long, i had it on my disk sometime, but as you know i do not test other bots very long at all.

BSP is some sort of waypointed ofcourse, since it uses eventually a 'chain' of information to get to positions (waypoints) to navigate through a map. (As asp said).

Totally unwaypointed is doable i guess, though it also requires some sort of memory system so a bot does not make mistakes often in U shaped rooms...

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

Right now in Algebra 3 (don't know why the course is called that when its has nothing to do with algebra) we are learning about tree graphs, Prim's algorithm.

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

And while take a flick through my printed lecture notes I see something called Eulerian graphs, disjoint cycles, and vertex colouring. I guess I will have to wait for my lecturer to explain this, cause he gives us proofs and background then explains and gives examples during lectures.

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

@stefan and asp, I was talking of my bot before Amsterdam ; back then I was not using anything waypoint related (waypoints, navmesh, BSP stuff). The navigation was exclusively based on tracelines (FOV scan), and the bot could navigate de_dust and de_dust2 almost as well as the best bots at the moment. But yeah, right now the BSP stuff I'm making is totally waypoint related. It's been a big switch since Tub showed us that.

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

yes, i know, but back then you were thinking about memory nodes and you refused to see them as some sort of wp system :)

anyway, back to topic:

@lethal : maybe you could posts links to your lecture notes ( if there are any ) or scripts. might be interesting to take a look at them :)

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

I hope I don't in bother for this, oh well. He has them set to global so I suppose he doesn't mind anyone outside of uni taking a look at them;
Thats the base web site for students looking for thins to read : http://www.ma.hw.ac.uk/~markl/teaching/F11ME3/
And here is the lecture notes in pdf :
http://www.ma.hw.ac.uk/~markl/teachi...lgebra3lec.pdf

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

We didn't forget , but we cant get it :-/ . Maybe upload a copy into the filebase ?

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

We should just for fun retry that one time... I think its not impossible to do it via that way. Using some sort of memory system.... so it will probably become some sort of waypointed, yet unwaypointed, navigation system. (since you do not rely on waypoints to create paths entirely... if you get what i mean)

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

How about on the fly navigation. bot considers options before it, ie down straight corridor with corner on left, bot hugs right wall till it reaches corner. With an added specialty looks back down the corridor where it just came from to check for enemies, then procedes not relying on a predetermined route, I know a little vague but I don't know what you guys can do with programming so I leave that bit to you's.

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

that resembles the "robust trace" navigation method described in the wiki, though it would not be tracing up to a particular destination. I think someone did a modified version of the HPB_bot that sorta worked that way. But it's still a very robotic-like way of moving...

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

Well another suggestion could be to have bots behave like woodlice.
Mainly because I remember a project in Bio I had to do with the behaviour patterns in woodlice; turn alternation.
Could that be adotped into bots.
Maybe for bots to behave like humans you would need to begin at the basics of choice.

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

one of the realbot versions in the ancient times had something like that. It basicly even used 'beacons' to 'help' the bot to move from beacon to beacon to eventually get to the goal...

it was something like this:

- determine angle to goal
- face it
- check if that angle is not blocked by x radius
- if so, do a scan of 180 degrees and go for the 'most far reached' traceline.

So basicly, the bot would go for the most 'farest' traceline, as that is the most 'safe' way. (walls-wise). The theory was, when you enter a corner with 1 or 2 ways T one or L one, you could basicly have the bot turn around because of the 'farest traceline' technique. This only worked half...

why? Because due you want the bot to go somewhere (goal...) you sometimes forced a bot into a dead end, and the bot would do neatly a turn (to prevent collission with walls) and then after a few seconds get back. This is the same as you get with any path finding algorithm. Mostly noticable with First Depth Search.

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

Would a Eulerian mode help?

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

maybe, if we knew what you mean :D ... euler did quite a lot of stuff :P

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

sorry about the ambiguatity, however you spell that hehe, I mean Eulerian bridge problem type of mode, where the nodes connected could be selected and the bot takes each connection only once and therefore may not visit the same area twice, its a mode because it will be useful when the bot is trying to hide or search for the remaining player.

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

That would work only if all maps were guaranteed to have an even number of entrances/exits per room. Else you would easily trap your bot in one of them. Besides, when searching for the remaining player, the bot is not searching for a static object but for a moving entity.

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

Just pondering thats all.
Would a overall mind be possible?
That would make the bots play as teams but I wouldn't know how to make such a 'object'. With only one mind doing the processing it would therefore make the bots follow its commands based on the other bots encounters, well it could; I am thinking a long the lines of a hive mind controller. Worth experimenting with?
ps hope I don't sound stupid...

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

Yes, that's a very common technique of implementing a squad AI. But it is preferrable to delegate the control not to a hive mind, but to a squad member who will be the "officer in charge", so as to ensure the inputs are the same a human would have. Else the AI can look like it's cheating.

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

In a racing game Euler algorithm taking the quickest waypoints on the road would work. Wonder if they already used it in games like toca and other racing games.
You could use it and eliminate each route after each lap so the npc cars don't have the same lap over and over again.

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

Instead of tossing around a lot of bizarre ideas that may or may not work, why don't you read more about A* ? This is THE only algorithm you need for pathfinding, there's nothing better at the moment so don't bother trying something else... :)

Unless you want to develop your own algorithm, but forget about what you've been taught then :)

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

there is proof that A* is optimal ( when having an optimal heuristic ) , so I doubt that there'll be comparable better algorithms in the near future. maybe somewhen on quantum computers, but not now.

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

i don't see how another algorithm can be better then A* ;) A* gives all you need. Ow, you can basicly strip A* a bit down to get the same effect. Some call it 'First Depth Search", which is true , but you have to do some optimization afterwards to get good results as well. Download the RealBot source code for information about its path finder.. it could help you a bit.

Nevertheless, you should really read the articles proposed ;)

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

I've been expanding the wiki article about pathfinding, check it out too...

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

Ok I will have a look at the wiki once I figure out how to look at some of the bits since they are asking me to login in with email address and stuff ???,
Also I learned a tad about vertex coloring, at least I think it was that, didn't someone use something similar to find 'faces' for the bots to walk on?

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

Okay so I read about A*, interesting read for since my Bac of Maths with Physics takes me nowhere near computer science stuff so I harly see any off the stuff we work with (well at least the some the basic stuff) except when I am asked to do crap stuff like show normal distribution with a computer programs drawing graphs for me (Statistics, yuck no-one could possibly enjoy it).