Putting entities into stacks

DusterdooSmock · Post by **DusterdooSmock** » Thu Jul 21, 2011 2:42 am

Hey guys, I'm working on coding my own bot from scratch. So far, he's coming along great; he roams the map using waypoints, follows and attacks when he sees you, and goes back to roaming the map if he loses sight of you.

But, unfortunately, I'm having one problem with it.
- Each time he passes a waypoint, the game sets that point to a value that allows him to ignore the waypoint that he just passed, and move on to the next one. But, I'm having an issue with this, as he always "bounces" between the first two waypoints he sees.

I was told to create a system where the bot puts the waypoints into a stack, but to be honest with you, i dont know how to do that.

andrewj · Post by **andrewj** » Thu Jul 21, 2011 5:26 am

I think by stack it means remembering the last 4 (for example) waypoints that the bot visited.

Something like these fields:

Code: Select all

.entity lastway1;
.entity lastway2;
.entity lastway3;
.entity lastway4;

You can check if the bot has visited any of those places before to decide where to go next.

When the bot visits a new waypoint you need to add it to this "stack", something like:

Code: Select all

void() remember_way(entity way)
{
  self.lastway4 = self.lastway3;
  self.lastway3 = self.lastway2;
  self.lastway2 = self.lastway1;
  self.lastway1 = way;
}

DusterdooSmock · Post by **DusterdooSmock** » Thu Jul 21, 2011 1:50 pm

I tried that, and it still did the same thing; he goes to the first, then to the second, then back to the first. Over and over.

Maybe it was the way i checked it, i dunno..

Code: Select all

float(entity way) WaypointCheck = 
{
	if(way == self.lastway3)
		return FALSE;
	else if(way == self.lastway2)
		return FALSE;
	else if(way == self.lastway1)
		return FALSE;
	else
		return TRUE;
};

Then i have this when he tries to find a new waypoint:

Code: Select all

void() BotFindWaypoint = 
{
	local entity point;
	
	point = findradius(self.origin, 240);
	
	while(point)
	{
		if(WaypointCheck(point) == TRUE)
		{
			if(point.classname == "waypoint")
				self.objective = point;
		}
			
		point = point.chain;
	}
};

Electro · Post by **Electro** » Fri Jul 22, 2011 12:17 am

Cool! Someone else is doing bot stuff too

Ok first of all, need to get some terminology sorted.

Stack = list of things
Push = add to the stack
Pop = remove from the stack

Usually when you push/pop things from a stack, you do it from either the top or the bottom. eg. Push to the top, pop from the bottom.

Now when someone told you the waypoints should be on a stack, generally that's a good way to go about it. For QuakeC though, with the general lack of arrays (you can however use arrays now thanks to new fancy compilers!), there is another way to go about things.

What Frikbot does, and what I was doing for Shockbot, is instead of having a massive additional list of waypoints that the bot intends to visit... flag each waypoint with the bots unique id. So when you figure out the path you want the bot to take, flag each waypoint that he will take on his path. Make the first waypoint he needs to visit the goal, then when he touches his goal (or gets within a certain distance threshold), remove the flag from that one. Now, check that waypoints list of connections to find which one has the flag on it out of those. Make the new linked one from there the new goal.

DusterdooSmock · Post by **DusterdooSmock** » Fri Jul 22, 2011 3:49 am

Electro wrote:Cool! Someone else is doing bot stuff too

Ok first of all, need to get some terminology sorted.

Stack = list of things
Push = add to the stack
Pop = remove from the stack

Usually when you push/pop things from a stack, you do it from either the top or the bottom. eg. Push to the top, pop from the bottom.

Now when someone told you the waypoints should be on a stack, generally that's a good way to go about it. For QuakeC though, with the general lack of arrays (you can however use arrays now thanks to new fancy compilers!), there is another way to go about things.

What Frikbot does, and what I was doing for Shockbot, is instead of having a massive additional list of waypoints that the bot intends to visit... flag each waypoint with the bots unique id. So when you figure out the path you want the bot to take, flag each waypoint that he will take on his path. Make the first waypoint he needs to visit the goal, then when he touches his goal (or gets within a certain distance threshold), remove the flag from that one. Now, check that waypoints list of connections to find which one has the flag on it out of those. Make the new linked one from there the new goal.

Thanks to your help, and a little help I got from FrikaC earlier today, I have a basic version of my bot up and running.

Here, take a look:
http://www.moddb.com/games/fps/videos/fps-new-ai-test1

Electro · Post by **Electro** » Fri Jul 22, 2011 4:17 am

No worries, glad to help out

Looks good so far! Can't wait to see it progress.

Feel free to post any other AI ideas/questions etc. Artificial Intelligence is my favourite part of coding, and that section on the forums here is a little dry at the moment.

daemonicky · Post by **daemonicky** » Fri Jul 22, 2011 5:33 pm

What about implementing Collaborative Diffusion?

There is explanation :
http://scalablegamedesign.cs.colorado.e ... _Diffusion

Google has some videos too, this Lagomorph:
http://www.google.com/search?q=collaborative+diffusion

metlslime · Post by **metlslime** » Fri Jul 22, 2011 5:51 pm

Electro wrote:Usually when you push/pop things from a stack, you do it from either the top or the bottom. eg. Push to the top, pop from the bottom.

This describes a Queue. A Stack gets popped from the top, not the bottom.

frag.machine · Post by **frag.machine** » Mon Jul 25, 2011 3:40 am

LIFO = last in, first out (stack)
FIFO = first in, first out (queue)

Both are useful data structures.

Electro · Post by **Electro** » Mon Jul 25, 2011 4:54 am

Cool, cheers