Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting
FAQ Members List Calendar Today's Posts

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 04-16-2011, 04:14 AM
kingcj kingcj is offline
Registered User
kingcj's Avatar
Join Date: Apr 2006
Location: TN
Posts: 114
kingcj will become famous soon enough
Send a message via MSN to kingcj
NPC Path-Finding Help

I've been working with a baddy and am trying to get him to move around something instead of continually trying to run that blocking tile over. I am not sure how it would be done so I am coming to forums for a little help. I have constructed small maze which is like 3 or 4 turns, and I would like the NPC to navigate through this small, not complicated "maze."

With that said, I don't want to program in level coordinates because I want the NPC to navigate by itself. I am just really unsure of how to approach this. I can only speculate that the NPC would need some sort of mapping function that would extend from the npc in all directions to allow it to correctly navigate the maze.

Thanks For Any Help, It is Appreciated.
__________________
Zie

"It is not necessary to change. Survival is not mandatory." - W. Edwards Deming
Reply With Quote
  #2  
Old 04-16-2011, 04:29 AM
Twinny Twinny is offline
My empire of dirt
Twinny's Avatar
Join Date: Mar 2006
Location: Australia
Posts: 2,422
Twinny is just really niceTwinny is just really nice
Send a message via AIM to Twinny
Google A* and you can get an idea how to implement simple pathfinding. I believe there is already an example in the code gallery that is based on A* :o
Reply With Quote
  #3  
Old 04-16-2011, 04:33 AM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
Using A* for a maze is a good way to not get through the maze. A* uses a heuristic in the name of performance, and that heuristic doesn't know much about how to solve a maze.

Look up the "wall follower" rule if you want to solve a maze.


Regardless, for any method, you will need to somehow read in the level tiles and convert that into a 2D array of paths and walls. Then on that array, you find the right path, and then convert the path back into directions to move the NPC.
Reply With Quote
  #4  
Old 04-16-2011, 04:45 AM
kingcj kingcj is offline
Registered User
kingcj's Avatar
Join Date: Apr 2006
Location: TN
Posts: 114
kingcj will become famous soon enough
Send a message via MSN to kingcj
Ok, A* googled doesn't really give me anything related to scripting. Wall follower rule pulls up fine. My question now is how to read the in level tiles and convert to an array?

Awhile back I asked about a circle polygon type deal, and I was going to use the circle to make the array, but I am not sure how to get the level tiles into the array?

My next question is, if this does work, how much lag would result from it? So, would it be possible for a server full of this type of npc to be walking around and not produce an enormous amount of lag?
__________________
Zie

"It is not necessary to change. Survival is not mandatory." - W. Edwards Deming
Reply With Quote
  #5  
Old 04-16-2011, 05:02 AM
fowlplay4 fowlplay4 is offline
team canada
fowlplay4's Avatar
Join Date: Jul 2004
Location: Canada
Posts: 5,200
fowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond repute
Here's how Zodiac's baddy movement works. It doesn't move directly to the player in one step but instead takes it in strides of 0.5 seconds of movement at max.

PHP Code:
// Removed Zodiac Specific Code
function onPlayerEnters() {
  if (!
this.on) {
    
this.on true;
    
onTimeout();
  }
}

function 
onTimeout() {
  if (
players.size() < 1) {
    
this.on false;
    return;
  }
  
chase(players[0]);
}

function 
chase(target) {
  
// Set Speed
  
temp.speed .3;
    
  
// Calculate Position in front of Target
  
temp.tpos = {target.vecx(this.dir)*2.5target.vecy(this.dir)*2.5};
  
// Calculate Distance to Target
  
temp.dist = ((temp.tpos[0] - x)^+ (temp.tpos[1] - y)^2)^.5;
  
// Calculate Steps Required 
  
temp.steps temp.dist temp.speed;
  
// Avoid Too Many Steps
  
if (temp.steps 10)
    
temp.steps 10;

  
// Calculate Angle towards Target
  // Random helps prevent clumping of npcs
  
temp.angle getangle(temp.tpos[0] - xtemp.tpos[1] - y) + random(-0.2,0.2);
  
// Calculate the Delta
  
temp.dx cos(temp.angle) * temp.speed;
  
temp.dy = -sin(temp.angle) * temp.speed;

  
setcharani("walk"this.attr[2]);
  
move(temp.dx temp.stepstemp.dy temp.stepsint(temp.steps) * .058);

  
setTimer(int(temp.steps) * .05);
}

function 
onMovementFinished() {
  
setcharani("idle""");

Sure it still allows baddies to walk over walls but it's an even bigger issue when players can glitch them into corners and abuse the situation.
__________________
Quote:
Reply With Quote
  #6  
Old 04-16-2011, 05:25 AM
kingcj kingcj is offline
Registered User
kingcj's Avatar
Join Date: Apr 2006
Location: TN
Posts: 114
kingcj will become famous soon enough
Send a message via MSN to kingcj
Quote:
Originally Posted by fowlplay4 View Post
Here's how Zodiac's baddy movement works....
Ok but I want the rat to run the race fairly. This "baddy" wouldn't be used for fighting. I have programmed in an area, and I want the npc to "wander" into that area through the maze. It would be like an AI for the NPC. So say the NPC is a farm hand and works in the field. I want the NPC to walk to work without being caught at the gate, and then be able to get back home after quitting time without planning its every move. This way it would be easy to implement a "living" server.
__________________
Zie

"It is not necessary to change. Survival is not mandatory." - W. Edwards Deming
Reply With Quote
  #7  
Old 04-16-2011, 05:54 AM
fowlplay4 fowlplay4 is offline
team canada
fowlplay4's Avatar
Join Date: Jul 2004
Location: Canada
Posts: 5,200
fowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond repute
Quote:
Originally Posted by kingcj View Post
Ok but I want the rat to run the race fairly. This "baddy" wouldn't be used for fighting. I have programmed in an area, and I want the npc to "wander" into that area through the maze. It would be like an AI for the NPC. So say the NPC is a farm hand and works in the field. I want the NPC to walk to work without being caught at the gate, and then be able to get back home after quitting time without planning its every move. This way it would be easy to implement a "living" server.
Different scenarios have different solutions.

Also I should note that you're venturing into an area that's more 'theory' than language-specific and your ability will require you to convert that theory into actual script.
__________________
Quote:
Reply With Quote
  #8  
Old 04-16-2011, 09:57 PM
kingcj kingcj is offline
Registered User
kingcj's Avatar
Join Date: Apr 2006
Location: TN
Posts: 114
kingcj will become famous soon enough
Send a message via MSN to kingcj
Before I do this I wanted to run it by someone and possibly get some feedback.
Could I set a group of variables up to check the tiles and then direct the npc to non-blocking tiles closest to its destination? It sounds possible, but it would be a lot of code and then some equations to determine which non-blocking tiles are closer to the npcs destination. Also is there a way to cycle through the variables to input them into the equation? (such as with a loop?)
__________________
Zie

"It is not necessary to change. Survival is not mandatory." - W. Edwards Deming
Reply With Quote
  #9  
Old 04-16-2011, 10:29 PM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
Quote:
Originally Posted by kingcj View Post
Before I do this I wanted to run it by someone and possibly get some feedback.
Could I set a group of variables up to check the tiles and then direct the npc to non-blocking tiles closest to its destination? It sounds possible, but it would be a lot of code and then some equations to determine which non-blocking tiles are closer to the npcs destination. Also is there a way to cycle through the variables to input them into the equation? (such as with a loop?)
You are on your way to describing A*. Again, this won't work well for a maze.

If you are doing some other sort of path finding where you don't need to get to your destination, then A* is your best bet.
Reply With Quote
  #10  
Old 04-16-2011, 10:49 PM
salesman salesman is offline
Finger lickin' good.
salesman's Avatar
Join Date: Nov 2008
Location: Colorado
Posts: 1,865
salesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud ofsalesman has much to be proud of
use the built in findpathinarray() function
__________________
Reply With Quote
  #11  
Old 04-16-2011, 11:33 PM
kingcj kingcj is offline
Registered User
kingcj's Avatar
Join Date: Apr 2006
Location: TN
Posts: 114
kingcj will become famous soon enough
Send a message via MSN to kingcj
Quote:
Originally Posted by WhiteDragon View Post
You are on your way to descibing A*. Again, this won't work well for a maze.

If you are doing some other sort of path finding where you don't need to get to your destination, then A* is your best bet.
Thanks for the link, but it isn't really a maze. It's just a small set of turns and narrow non-blocking tiles. I really just want the NPC to navigate to its destination efficiently, and it seems that this would be a good way to do it. I haven't seen/thought of any other way to do this.

Quote:
Originally Posted by salesman View Post
use the built in findpathinarray() function
Ah, I didn't even realize this existed. I've looked it up, but it does a path limit. Is that how many tiles the npc is allowed to travel? Also I'm not quite sure about the obj used in the script? Is it the tile type or hex codes of tiles? It isn't very clear to me.

Thanks for your Help
__________________
Zie

"It is not necessary to change. Survival is not mandatory." - W. Edwards Deming
Reply With Quote
Reply


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 Off

Forum Jump


All times are GMT +2. The time now is 08:51 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.