Page 1 of 1

How do Waypoints work?

Posted: Tue Nov 02, 2010 1:02 am
by Mexicouger
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

Posted: Tue Nov 02, 2010 1:14 am
by leileilol
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)

Re: How do Waypoints work?

Posted: Tue Nov 02, 2010 11:28 am
by frag.machine
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.

Posted: Tue Nov 02, 2010 6:04 pm
by scar3crow
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).

Re: How do Waypoints work?

Posted: Tue Nov 02, 2010 10:25 pm
by Mexicouger
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.

Posted: Tue Nov 02, 2010 11:38 pm
by blubswillrule
@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

Posted: Tue Nov 02, 2010 11:43 pm
by Mexicouger
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.

Posted: Wed Nov 03, 2010 1:37 am
by blubswillrule
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)

Posted: Tue Aug 16, 2011 2:20 am
by DusterdooSmock
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.

Posted: Tue Aug 16, 2011 5:20 am
by Electro
What's the moddb page link?

Posted: Tue Aug 16, 2011 7:41 pm
by DusterdooSmock
Electro wrote:What's the moddb page link?
http://moddb.com/games/fps/
I think you already saw the video though...

Posted: Tue Aug 16, 2011 10:18 pm
by Electro
ohh ok yep, i have :)

Re: How do Waypoints work?

Posted: Wed Aug 24, 2011 1:12 pm
by daemonicky
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 .