.:: Bots United ::.  
filebase forums irc server wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps waypoints yapb

Go Back   .:: Bots United ::. > YappA > The Agora
The Agora This is the place to go if you have suggestions, or if you want to participate in Council discussions. Everyone is welcome!

Reply
 
Thread Tools
When developing Bots what do you used, ie whats in the code?
Old
  (#1)
Lethal
Member
 
Lethal's Avatar
 
Status: Offline
Posts: 163
Join Date: Jun 2004
Location: Scotland
Default When developing Bots what do you used, ie whats in the code? - 21-04-2005

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?
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#2)
Rick
Council Member
 
Rick's Avatar
 
Status: Offline
Posts: 689
Join Date: Dec 2003
Location: Holland
Default Re: When developing Bots what do you used, ie whats in the code? - 21-04-2005

Quote:
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
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#3)
Lethal
Member
 
Lethal's Avatar
 
Status: Offline
Posts: 163
Join Date: Jun 2004
Location: Scotland
Default Re: When developing Bots what do you used, ie whats in the code? - 21-04-2005

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.
Attached Thumbnails
Click image for larger version

Name:	untitled.jpg
Views:	215
Size:	28.0 KB
ID:	668  

Last edited by Lethal; 21-04-2005 at 23:12..
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#4)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: When developing Bots what do you used, ie whats in the code? - 22-04-2005

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


  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#5)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 4643'60N 043'0W 0.187A
Default Re: When developing Bots what do you used, ie whats in the code? - 22-04-2005

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.



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#6)
Lethal
Member
 
Lethal's Avatar
 
Status: Offline
Posts: 163
Join Date: Jun 2004
Location: Scotland
Default Re: When developing Bots what do you used, ie whats in the code? - 03-05-2005

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?
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#7)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: When developing Bots what do you used, ie whats in the code? - 03-05-2005

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


  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#8)
stefanhendriks
RealBot Author
 
stefanhendriks's Avatar
 
Status: Offline
Posts: 3,083
Join Date: Nov 2003
Location: Netherlands
Default Re: When developing Bots what do you used, ie whats in the code? - 03-05-2005

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


Author of RealBot, "Arrakis" and "Dune 2 - The Maker" | co-Founder of Bots-United | Fundynamic | Blog | E-Mail me
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#9)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 4643'60N 043'0W 0.187A
Default Re: When developing Bots what do you used, ie whats in the code? - 03-05-2005

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



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Re: When developing Bots what do you used, ie whats in the code?
Old
  (#10)
stefanhendriks
RealBot Author
 
stefanhendriks's Avatar
 
Status: Offline
Posts: 3,083
Join Date: Nov 2003
Location: Netherlands
Default Re: When developing Bots what do you used, ie whats in the code? - 03-05-2005

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


Author of RealBot, "Arrakis" and "Dune 2 - The Maker" | co-Founder of Bots-United | Fundynamic | Blog | E-Mail me
  
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com