Using minetest.find_path for mob pathfinding

[MirceaKitsune]

Yesterday I was surprised to find out that Minetest should now have a pathfinding system. I'd rather not wonder how CPU hungry such a thing is... but either way, I'd like to add an option for my mob mods to use it. Problem is that the engine only provides half of the solution, while the rest must be done in Lua and I'm not quite sure how.

minetest.find_path(pos1,pos2,searchdistance,max_jump,max_drop,algorithm)
^ -> table containing path
^ returns a table of 3d points representing a path from pos1 to pos2 or nil
^ pos1: start position
^ pos2: end position
^ searchdistance: number of blocks to search in each direction
^ max_jump: maximum height difference to consider walkable
^ max_drop: maximum height difference to consider droppable
^ algorithm: A*_noprefetch(default), A*, Dijkstra

From what I understand, that returns the list of positions an entity must go through. So far so good... but what's the simplest and most efficient way to make a Lua entity actually follow this array of points? How can an entity go to the first point, detect that it arrived there, then head toward the second point, and so on?

Things to keep in mind: The path and point list is constantly refreshed, to account for cases where a block has been placed or removed and the path must therefore change. The mob must also be able to adapt if someone pushes it off trajectory, for example by digging a block from under its feet and letting it fall. My mobs are otherwise based on PA's simplemobs... so currently, a mob walks toward a player it's attacking by looking toward that player (changing rotation) and being given a forward velocity.

[Sokomine]

Sapiers mobf AFAIK has some pathfinding. Try to locate a trader and "buy" a guard or archer from him. Another mobs mod that seems to come with good pathfinding seems to be stu's npcf. Mobs from there where able to follow me without jumping into every hole on the way. Simple mobs does not aim at good pathfinding.

[philipbenr]

I'm sorry I don't know that much. I honestly wish I could help, but this is sort of over my head. ;) Anyhow, I hope that you succeed with whatever it is you're doing.

[bdjnk]

...Minetest should now have a pathfinding system. I'd rather not wonder how CPU hungry such a thing is...

It's likely well written, in c++, and thus relatively fast and efficient.

...what's the simplest and most efficient way to make a Lua entity actually follow this array of points? How can an entity go to the first point, detect that it arrived there, then head toward the second point, and so on?

Does something like this not work?

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local path = minetest.find_path(mob.getpos(), player.getpos(), ...)
for i,pos in ipairs(path) do
  mob.moveto(pos, ...)
end

where 'mob' is a ObjectRef

...The path and point list is constantly refreshed, to account for cases where a block has been placed or removed and the path must therefore change. The mob must also be able to adapt if someone pushes it off trajectory, for example by digging a block from under its feet and letting it fall.

It you want a simple (inefficient) way to do this, calculate the 'path' within the loop, perhaps like this.

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local path = minetest.find_path(mob.getpos(), player.getpos(), ...)
while path do -- not nil
  mob.moveto(next(path), ...)
  path = minetest.find_path(mob.getpos(), player.getpos(), ...)
end


[rubenwardy]

You only need to recalculate when a block is placed or removed which is part of or under the node graph.

[MirceaKitsune]

I didn't know about the minetest.moveto function... that clears things up a lot! Like I said, my mob system currently changes the rotation of the mob and assigns a forward velocity. I assume SimpleMobs was written before moveto existed, or considered it too costly. Either way, I should modify the movement to use this for sure!

Only thing I really wish to avoid is calling minetest.find_path inside the loop however. C++ or not, I don't think such a calculation can be very light. The function containing this code does however re-run constantly, limited by an AI think rate (eg: 0.1 seconds)... so even when the path function is outside of the loop it's refreshed as often as it needs to be.

[EDIT] Already found the first problem: How do you specify a velocity for moveto? It only takes a position, but doesn't let you mention at which speed the entity walks there. Mobs have various walking speeds and this is mandatory.

[bdjnk]

Yeah, that loop is really stupid. It was absurdly late and I was posting in a haze of exhaustion.

If you post your work in progress, I would like to take a look.

[MirceaKitsune]

Alright, I'm trying this now. I have created the code, and posted what I hoped would be the final version below. Please take a look at it and let me know what's wrong and what to correct.

How it works: The code executes in a loop... for my test mobs that's every 0.25 seconds. The point list is first obtained with minetest.find_path. The first entry is then deleted, since that's probably the mob's own position. Then we look at the next entry; If it's closer than 1m in all directions, it means it's a destination we have reached, so we remove it from the table. Then we simply set the destination to the first entry in the final table.

What fails: Mobs still walk toward the player they are following, and succeed if it's on a straight surface... so part of it is a success. But if the player walks up a stair then goes across a ledge, mobs don't attempt to follow that path. They instead try to walk directly toward the player above them, exactly like the old behavior.

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

   -- s is the position of the mob
   -- self.v_pos is the destination we want to get to
   -- self.v_path is the list returned by minetest.find_path
   -- this code executes approximately each 0.25 seconds

   if self.v_pos then
      local dst = self.v_pos
      if minetest.setting_getbool("pathfinding") then
         self.v_path = minetest.find_path(s, self.v_pos, self.traits.vision, 1, 5, nil)
         if self.v_path and #self.v_path > 1 then
            -- the first entry is the current position, ignore it
            table.remove(self.v_path, 1)

            -- if the next entry is closer than 1 block, it means it's a destination we have reached
            if math.abs(s.x - self.v_path[1].x) <= 1 and
            math.abs(s.y - self.v_path[1].y) <= 1 and
            math.abs(s.z - self.v_path[1].z) <= 1 then
               table.remove(self.v_path, 1)
            end

            if #self.v_path > 0 then
               dst = self.v_path[1]
            end
         end
      end

      -- handle orientation and movement
      local vec = {x = dst.x - s.x, y = dst.y - s.y, z = dst.z - s.z}
      local yaw = math.atan(vec.z / vec.x) + math.pi / 2
      if dst.x > s.x then
         yaw = yaw + math.pi
      end
      self.object:setyaw(yaw)
   end
   self.set_velocity(self, self.v_speed)

[MirceaKitsune]

Just an update: You can disregard my above post. The Lua function itself appears to be correct. The problem is with the engine function, which is still very broken in latest GIT master. I made a report of the issue over here.