Graal Forums - NPC Path-Finding Help

Graal Forums (https://forums.graalonline.com/forums/index.php)

- NPC Scripting (https://forums.graalonline.com/forums/forumdisplay.php?f=8)

- - NPC Path-Finding Help (https://forums.graalonline.com/forums/showthread.php?t=134262841)

kingcj

04-16-2011 04:14 AM

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.

Twinny

04-16-2011 04:29 AM

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

WhiteDragon

04-16-2011 04:33 AM

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.

kingcj

04-16-2011 04:45 AM

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?

fowlplay4

04-16-2011 05:02 AM

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.x - vecx(this.dir)*2.5, target.y - vecy(this.dir)*2.5};

  // Calculate Distance to Target

  temp.dist = ((temp.tpos[0] - x)^2 + (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] - x, temp.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.steps, temp.dy * temp.steps, int(temp.steps) * .05, 8);



  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.

kingcj

04-16-2011 05:25 AM

Quote:

Originally Posted by fowlplay4 (Post 1643625)

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.

fowlplay4

04-16-2011 05:54 AM

Quote:

Originally Posted by kingcj (Post 1643630)

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.

kingcj

04-16-2011 09:57 PM

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?)

WhiteDragon

04-16-2011 10:29 PM

Quote:

Originally Posted by kingcj (Post 1643768)

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.

salesman

04-16-2011 10:49 PM

use the built in findpathinarray() function

kingcj

04-16-2011 11:33 PM

Quote:

Originally Posted by WhiteDragon (Post 1643782)

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 (Post 1643786)

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

All times are GMT +2. The time now is 12:22 AM.