Forum

How do Waypoints work?

Discuss Artificial Intelligence and Bot programming.

Moderator: InsideQC Admins

How do Waypoints work?

Postby Mexicouger » Tue Nov 02, 2010 1:02 am

It really doesn't phase me how Waypoints work.

Do the bots just randomly pick a waypoint and walk to it? Do they walk to the waypoints in the order they are put? Do they just pick the nearest waypoint and walk it? What if a bot gets attracted by a player, Will he exit the waypoint to fight the player?

I don't expect many of those Questions to be answered. They are just some of the many questions that flow through my head and make me confused on how waypoints work. Please explain to me how these things work so I can appreciate them
User avatar
Mexicouger
 
Posts: 514
Joined: Sat May 01, 2010 10:12 pm

Postby leileilol » Tue Nov 02, 2010 1:14 am

The answers are in your questions.

Fuzzy logic makes great pretend thinking. Consider the word Artificial in the term Artificial Intelligence.

Please keep in mind not all bots operate with waypoints. Some (like Quake3's bots, and Quake2 gladiator bots) use an area awareness system to get around the map sensing the entities in them and according to their predefined personal item priority weights. More recently Left4Dead uses a similar AAS system for the ai survivors and the infected (and they hyped it in a pdf like they invented it lol)
i should not be here
leileilol
 
Posts: 2783
Joined: Fri Oct 15, 2004 3:23 am

Re: How do Waypoints work?

Postby frag.machine » Tue Nov 02, 2010 11:28 am

Mexicouger wrote:It really doesn't phase me how Waypoints work.

Do the bots just randomly pick a waypoint and walk to it? Do they walk to the waypoints in the order they are put? Do they just pick the nearest waypoint and walk it? What if a bot gets attracted by a player, Will he exit the waypoint to fight the player?

I don't expect many of those Questions to be answered. They are just some of the many questions that flow through my head and make me confused on how waypoints work. Please explain to me how these things work so I can appreciate them


First, you should be more specific: are you talking about a particular implementation of waypoints - like in Frikbot waypoints ?

By definition a waypoint is just a kind of entity that can be chained to others and acts like a "trail" to the bots. On top that, you can add a lot of additional hints like "the next waypoint lies beyond a chasm, so jump to get there" or "to reach the next waypoint first press that button to open that door".

Usually, waypoints are closed circuits, that's mean the last waypoint chains back to the first, since a bot can potentially spawn in any spot in the map and just pick the nearest waypoint. You can have variations on this, like more than one circuit.

A waypoint system allows the bot to navigate thru all important areas in a map so it can get ammo, weapons, etc. Typically during this roaming mode, if the bot sees a player it leaves the waypoint trail and chase the player. Once the player is killed, the bot tracks the nearest waypoint and resumes the roaming mode.

As leileilol told you, games like Q3A uses a different navigation algorithm: instead point-like entities, the map compiling tools build something like a chain of volumetric polyhedrons representing the "navigable areas" in the map. The bot just pick the nearest and, starting from this area, picks the shortest path to its current target (a player, a weapon, a powerup, etc).

There are other mechanisms to help a bot to navigate thru a map, but the two above are quite common.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2063
Joined: Sat Nov 25, 2006 1:49 pm

Postby scar3crow » Tue Nov 02, 2010 6:04 pm

AFAIK, most ai presupposes the actor knows the environment. A bot in a Quake level that has decently developed pathing is going to know the rocket launcher's location, just like any moderately experienced player would. Monsters in Unreal if they saw you at a distance, knew which hallway to take, which teleporter to enter, which lift to ride, to get there the quickest. Such scenarios use waypoints, wayboxes or area information as a quick dataset to be processed through something like A* or the Lee algorithm for a fairly cheap way to figure the best one.

Regarding how they decide their manner (going to closest waypoint, following its chain - randomly picking one and following it, and randomly getting off - considering item value and working backwards through connections to themselves, etc), this is an opportunity to actually emulate various "personalities" in the bot, from a newbie, to the elite, and even the paranoid and eccentric play styles.

leilei; I skimmed the L4D pdf, it never dawned on me how similar it was to AAS (and in typical Valve fashion, they acted as if it was their own creation), but the whole thing smelled of "Isn't this old news?" Their ai always seemed like it was comparable to the Zeus bot with a few state checks to use inventory on each other, otherwise they just bobbed alongside players, only really doing much pathing if a distance was created between you and them (something you had to work at to do honestly).
...and all around me was the chaos of battle and the reek of running blood.... and for the first time in my life I knew true happiness.
User avatar
scar3crow
InsideQC Staff
 
Posts: 1054
Joined: Tue Jan 18, 2005 8:54 pm
Location: Alabama

Re: How do Waypoints work?

Postby Mexicouger » Tue Nov 02, 2010 10:25 pm

frag.machine wrote:
Mexicouger wrote:It really doesn't phase me how Waypoints work.

Do the bots just randomly pick a waypoint and walk to it? Do they walk to the waypoints in the order they are put? Do they just pick the nearest waypoint and walk it? What if a bot gets attracted by a player, Will he exit the waypoint to fight the player?

I don't expect many of those Questions to be answered. They are just some of the many questions that flow through my head and make me confused on how waypoints work. Please explain to me how these things work so I can appreciate them


First, you should be more specific: are you talking about a particular implementation of waypoints - like in Frikbot waypoints ?

By definition a waypoint is just a kind of entity that can be chained to others and acts like a "trail" to the bots. On top that, you can add a lot of additional hints like "the next waypoint lies beyond a chasm, so jump to get there" or "to reach the next waypoint first press that button to open that door".

Usually, waypoints are closed circuits, that's mean the last waypoint chains back to the first, since a bot can potentially spawn in any spot in the map and just pick the nearest waypoint. You can have variations on this, like more than one circuit.

A waypoint system allows the bot to navigate thru all important areas in a map so it can get ammo, weapons, etc. Typically during this roaming mode, if the bot sees a player it leaves the waypoint trail and chase the player. Once the player is killed, the bot tracks the nearest waypoint and resumes the roaming mode.

As leileilol told you, games like Q3A uses a different navigation algorithm: instead point-like entities, the map compiling tools build something like a chain of volumetric polyhedrons representing the "navigable areas" in the map. The bot just pick the nearest and, starting from this area, picks the shortest path to its current target (a player, a weapon, a powerup, etc).

There are other mechanisms to help a bot to navigate thru a map, but the two above are quite common.


Thanks! This cleared it all up. Waypoints seem pretty Handy to use, and I bet it takes less memory to use Waypoints than Just roaming bots Using the roaming Monsters on the tutorial Section.

I wonder how possible it is to add Waypoints to Monsters... I guess that is something I might work on later.
User avatar
Mexicouger
 
Posts: 514
Joined: Sat May 01, 2010 10:12 pm

Postby blubswillrule » Tue Nov 02, 2010 11:38 pm

@mexicougar
I would love you forever if you made monsters be able to use waypoints and pathfind :P

no, but seriously, I would do anything... even if that means making you some graphics, or paying you... or something. O_O
A truly rewarding experience for an AI coder: watching your ai navigate the map... makes all the time invested in the code worth it :)
User avatar
blubswillrule
 
Posts: 68
Joined: Mon Oct 04, 2010 9:08 pm
Location: Lincoln, California

Postby Mexicouger » Tue Nov 02, 2010 11:43 pm

blubswillrule wrote:@mexicougar
I would love you forever if you made monsters be able to use waypoints and pathfind :P

no, but seriously, I would do anything... even if that means making you some graphics, or paying you... or something. O_O


Haha, I don't know If I am that good of a AI coder yet :?
But I guess it is worth a try. Might be fun.
User avatar
Mexicouger
 
Posts: 514
Joined: Sat May 01, 2010 10:12 pm

Postby blubswillrule » Wed Nov 03, 2010 1:37 am

Mexicouger wrote:
blubswillrule wrote:@mexicougar
I would love you forever if you made monsters be able to use waypoints and pathfind :P

no, but seriously, I would do anything... even if that means making you some graphics, or paying you... or something. O_O


Haha, I don't know If I am that good of a AI coder yet :?
But I guess it is worth a try. Might be fun.


sweet, i'm willing to help you in any way that I can, so if you need anything, anything at all, maybe graphics or sumfin, I'm here for you
8)
A truly rewarding experience for an AI coder: watching your ai navigate the map... makes all the time invested in the code worth it :)
User avatar
blubswillrule
 
Posts: 68
Joined: Mon Oct 04, 2010 9:08 pm
Location: Lincoln, California

Postby DusterdooSmock » Tue Aug 16, 2011 2:20 am

blubswillrule wrote:@mexicougar
I would love you forever if you made monsters be able to use waypoints and pathfind :P

no, but seriously, I would do anything... even if that means making you some graphics, or paying you... or something. O_O


Blubs, if that offer still stands, PM me about it... I have some models that I need made.
And if you check the moddb page for FPS, you'll see that i recently programmed something like what you requested.
DusterdooSmock
 
Posts: 170
Joined: Thu Aug 19, 2010 9:58 pm

Postby Electro » Tue Aug 16, 2011 5:20 am

What's the moddb page link?
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
Electro
 
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia

Postby DusterdooSmock » Tue Aug 16, 2011 7:41 pm

Electro wrote:What's the moddb page link?

http://moddb.com/games/fps/
I think you already saw the video though...
DusterdooSmock
 
Posts: 170
Joined: Thu Aug 19, 2010 9:58 pm

Postby Electro » Tue Aug 16, 2011 10:18 pm

ohh ok yep, i have :)
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
Electro
 
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia

Re: How do Waypoints work?

Postby daemonicky » Wed Aug 24, 2011 1:12 pm

Mexicouger wrote:It really doesn't phase me how Waypoints work.


http://en.wikipedia.org/wiki/Graph_traversal

They select a goal node and then path from nearest node from where they are is found.
Goal node is selected based on some AI rules. Like, in Thief 2 nodes had "smell" or "noise" so nearest AI could check it. Basically "hey, THAT is the node I want because of my reasoning".
Nodes sometimes have some additional information, like that "smell" in Thief (IIRC it was there); well, they should because how else are You going to find THE ONE node, randomly? :)
Nodes are not necessarily a points in space, they might be areas (or these volumes...); areas are actually superior (ever seen NPC stuck behind invisible obstacles ...?).

Mexicouger wrote:Do the bots just randomly pick a waypoint and walk to it? Do they walk to the waypoints in the order they are put? Do they just pick the nearest waypoint and walk it? What if a bot gets attracted by a player, Will he exit the waypoint to fight the player?


How? That depends on Your phantasy and math skills. :)
For cool solution go there http://goo.gl/jqYkX .
Think, touch, movetype, solid, traceline ...
User avatar
daemonicky
 
Posts: 185
Joined: Wed Apr 13, 2011 1:34 pm


Return to Artificial Intelligence

Who is online

Users browsing this forum: No registered users and 1 guest