Archived

This topic is now archived and is closed to further replies.

npc movement algorithim???

This topic is 5110 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Im writing a 2d rpg and would like to know how to approach an algorithim to move npcs randomly. ps. Ive tried an approach with random numbers,but the npc object didnt move in a straight line.

Share this post


Link to post
Share on other sites
well, you could populate your level with a network of roads, and have goals for your npcs. (go to the shop, go to the neighbour, rob that guy...). You can generate the network using cells automatically. Then, use an A* search (Dijkstra algorithm), and your NPC will have a route traced for them to reach their goals. But don;t do that every frame. More like every 10 secs, or when the goal is reached.


Another way, is to move them going towards a direction, like you said. A simple path finding routine, if they get stuck. If you are stuck, always follow the wall to your left (or your right, but you have to choose). It a classic way of finding the exit to a closed maze, although probably not efficient, but you are assured to find the exit.

Share this post


Link to post
Share on other sites
The random should include both a random number for an action or direction, and a random number for time. Then you should not re-evaluate what to do until that time has passed.
This is a mistake that many games make. Read for example the postmortem for Trespasser in the Article & Resources section. They describe how the AI was supposed to work, based on the environment the dinosaur would decide what to do and where to walk. In the game this malfunctioned, after a while the dinosaur would end up in a position where several goals were attractive. It chose one action, then one frame later the dinosaur would have walked/turned a little, and the other goal would be more attractive. As a result it just vibrated in place, quickly moving back and forth a few inches 60 times/second.
These mistakes can be easily avoided if you add a timestamp for a next decision. Nobody needs NPC''s that decide to walk north and then within a second decide to walk south. With a time stamp of eg. 60 seconds until a next decision is made the behaviour would be much more consistent.

Share this post


Link to post
Share on other sites
Most NPC''s should just be state machines, so you shouldn''t ever really choose another path unless something monumental occurs.
Eg.

npc_check_state. if state ==
* walking:
- walk one more step towards goal.
- if at goal, set state ''choose goal''
- if attacked, set state ''handle attack''
* choose goal
- based on character motivations and knowledge, choose another
goal.
* handle attack
- if strong enough and not afraid, set state ''attack''
else set state ''run away''
* attack:
- find closest opponent. choose weapon, strike at opponent.
* run away:
- scream
- cower
- hide.

Share this post


Link to post
Share on other sites
If you mean the kind like in old SNES classics such as FF2, it''s pretty easy. Just have a direction and distance member of whatever class your NPC is part of. Set a random direction and a random distance (say, 1-6). Have the NPC in direction ''x'' for ''distance'' steps. Then start over.

You can also throw in occasional delays to avoid having a constant random movement, which would be a little unrealistic (but then again, realism isn''t really what those games were trying for )

Share this post


Link to post
Share on other sites
I used some of your ideas and now I have working npcs in my code.
Heres the code I used.

void drawnpc(BITMAP *bmp,int nx,int ny,int range)
{
int dir=rand()%4;
switch (dir)
{
case 0:
if(f==0){
NPC.dir=1;
NPC.x++;
a++;
if (a==range){
f=rand()%4;
a=0;
}
}
break;
case 1:
if(f==1){
NPC.dir=3;
NPC.x--;
b++;
if (b==range){
f=rand()%4;
b=0;
}
}
break;
case 2:
if(f==2){
NPC.dir=2;
NPC.y++;
c++;
if (c==range){
f=rand()%4;
c=0;
}
}
break;
case 3:
if(f==3){
NPC.dir=0;
NPC.y--;
d++;
if (d==range){
f=rand()%4;;
d=0;
}
}
break;
}
masked_blit(bmp, screen, 0, (NPC.dir*32), nx, ny, 32,32);
}

Thanks alot.

Share this post


Link to post
Share on other sites