NPCS That Follow and auto-pathing.

Avatar

By Hikari 25 Jan 2015 14:50

Member · 23 comments

Be it you following Professor Whoever, Person following you, Creature following you, or something as complicated as patching for NPCs during events.

How hard will that be to do?

Avatar

By ShadowApex 26 Jan 2015 21:01

Lead Developer · 374 comments

This feature is still in development and is currently an issue in our issue tracking system: https://git.tuxemon.org:3000/tuxemon/tuxemon/issues/14

Getting pathfinding and following working will require a moderate amount of work to get done.


Avatar

By josepharaoh99 17 Nov 2015 16:50

Champion · 295 comments

I've been messing around how to create a pathfind function, but the problem is- I DON'T KNOW PYTHON. But I do know C++, so I'll try to explain my ideas in an easy, clear form. But first I want to show some code for the wander state, which doesn't seem to work- correct me if it does.
In C++, it would look like this:

void wander(NPC npc, int y, int x)
{
int y2, x2;
x2 = x;
y2 = y;

int movement = rand() % 4;

if(movement == 0 && y2 + 1 != TYPE_COL && !((y2 + 1) > (y + 3))
{
   npc.move(1, 0);
   y2 += 1;
}   
if(movement == 1 && y2 - 1 != TYPE_COL && !((y2 - 1)> (y - 3))
{
   npc.move(-1, 0);
   y2 -= 1;
} 
if(movement == 2 && x2 + 1 != TYPE_COL && !((x2 + 1) > (x + 3))
{
   npc.move(0, 1);
   x2 += 1;
} 
if(movement == 3 && x2 - 1 != TYPE_COL && !((x2 - 1) > (x - 3))
{
   npc.move(0, -1);
   x2 -= 1;
}
}

This is what the code does: first is the function declaration that will require you to list the npc to be created and where it will placed(x, y). Then I duplicate x and y to x2 and y2, so that x and y will remain as the location of where the npc was first created, and x2 and y2 will be the location of where the npc moves to. This is so that the npc does not stray too far from where it was first created. Next, I generate a random number that will trigger a random movement; I divide the random number by four and assign the remainder to int movement. If movement = 0, the npc moves up, if it equals 1, the npc moves down, and so on. And you will notice that each if statement checks to see if the block that the npc is to move to does not contain a collision block (named as TYPE_COL for demonstration), so the npc does not walk on unwalkable blocks. Then the final condition is to check if the block the npc is to move to is not more than 3 (or it could be more) spaces away from where the npc was generated, so the npc does not stray too far. So, I don't know what this would look like in Python, but let me know if this helps at all. I am currently working on a pathfind logic function, but that's a bit harder smile .
P.S. This code would require a move action and a TYPE_COL (collision) block, which the game obviously has; I just don't know what they're called.

Last edited by josepharaoh99 (17 Nov 2015 16:53)


Multiple Media Producer
Jesus is God! http://www.upci.org/search

Avatar

By josepharaoh99 17 Nov 2015 17:19

Champion · 295 comments

Here's what I've scrapped up for pathfind:

void pathfind(NPC npc, int y2, int x2)
{
      if(y > y2)
      { 
         npc.move(1, 0);
      }
      if (y < y2)
      {
         npc.move(-1, 0);
      }
      if(x > x2)
      {
         npc.move(1, 0);
      }
      if (x < x2)
      {
         npc.move(-1, 0);
      }   
}

To use this function, you have to enter an npc to be moved and where you want it to move. If the location he needs to move is above where he currently is (if y > y2, y being the location where he is to go to, and y2 being the location he is to move to), he moves up. If it is below, he moves down, and so on. This same concept could apply to having a sprite follow you. But this script has a big problem- the npc would walk right through collision areas. So you would have to add something like the following at the top of the function:

 if((y + 1) == TYPE_COL) // if the space above the npc is a collision block
{
    npc.move(0, 1); // the npc moves to the right to avoid the collision area above him. 
}

You would have to wrap the if statements in a loop so that the computer keeps checking the conditions until the npc reaches the given location (or player). The major problem with the code patch is this: "What if the area to the right of the npc is also a collision block? Then he couldn't move to the right. So, to handle situations like this, you would have to write a lengthy list of if statements like this:

 if((y + 1) == TYPE_COL) // if the space above the npc is a collision block
{
    if((x + 1) == TYPE_COL) 
    {
        if ((x - 1) == TYPE_COL)

... and so on, and that still has problems. So what would this look like in Python? And how do you fix the collision problem? I hope I helped at least a little, even though I had about as many questions as answers wink

Last edited by josepharaoh99 (17 Nov 2015 17:19)


Multiple Media Producer
Jesus is God! http://www.upci.org/search

Avatar

By ShadowApex 18 Nov 2015 00:24

Lead Developer · 374 comments

In the future, try using the "[ code]" tag in your posts when showing any code. Helps make things easier to read.

You're right that wandering hasn't yet been implemented, but pathfinding has already been implemented by dtdannen. You can use the "pathfind" action in any map to make an NPC pathfind to a particular tile location. Right now pathfinding uses Breadth-first Search to find the path to its destination, which takes all the collision areas into account. This could be further optimized by using an A* Search algorithm instead, but the current algorithm has been working pretty well.

If you're interested in how it works, check out the source for the player module. Python is a super easy language to learn if you're interested. Check out some tutorials on codecademy.com if you want to try it out.

The wander behavior you described would be pretty simple to implement. It'd be nice to have some parameters the wander could take that dictates how far the npc should wander from its spawn point (or if it should wander as far as it wants to). The core.components.player.Npc class has a move() method that already automatically performs a collision check, so we'd just need to call that method to move in a random direction.


Avatar

By josepharaoh99 23 Nov 2015 17:22

Champion · 295 comments

I am having a weird error with pathfind, and I want to see if anyone else is having it. It does work! Yay! smile  But, when I use it, it duplicates the npc that is to move, and the original npc stays where it was created, while the new one walks on. So...what's going on? It is a very good working function, though


Multiple Media Producer
Jesus is God! http://www.upci.org/search

Avatar

By ShadowApex 23 Nov 2015 19:18

Lead Developer · 374 comments

I haven't seen this issue in my testing. Could you open an issue on GitHub with some more details and screenshots of the problem? Make sure to include how you're using your map events.

Thanks.


Avatar

By Kelvin 1 Dec 2015 21:13

Member · 44 comments

https://en.wikipedia.org/wiki/A*_search_algorithm

This might be useful. It's a commonly-used pathfinding algorithm that works well for tiled games. Although, I'm wondering if it would be faster to have a tile layer where 0 is empty space and anything else is treated as solid, rather than using rectangles marked "collision", since then it wouldn't have to identify the shape or do any hit detection like that, and could just check a boolean value for that tile, then just make the collision layer invisible.