NPC movement paths and obstacle detection

[llamazing]

I've been playing around with assigning path movements to npcs in order to have them follow a fixed route. The problem I'm running into is obstacle avoidance. Now it's easy enough to choose a route for the NPC that is clear of obstacles on the map, and I'd only have the NPCs moving around inside of towns where there are no enemies, so collisions with enemies are not a concern either. It's just collisions with the hero that I have to worry about.

I started off by setting set_ignore_obstacles(true) for the NPC movement. For the most part, that works. If the NPC's path goes through the hero's position then the hero will just get stuck for a little while until the NPC passes the hero, and it's just a little annoyance. The problem occurs if the hero happens to be standing where the NPCs path stops (and the NPC just stands in that spot for a while). Now the hero cannot move at all until the NPC starts a new path movement.

So then I played around with trying to push the hero out of the way when there's a collision with the NPC. So in the NPC movement's on_position_changed() function (any time the NPC moves), I check if the NPC and hero overlap with NPC:overlaps(hero, "overlapping"), and if they do, I assign a movement to the hero to nudge the hero out of the NPC's path.

I'm assuming that I need to move the hero one pixel at a time so that if the hero gets pushed over a 16x16 teletransporter (say inside a doorway), that the hero doesn't get pushed too far and skip the teletransporter. Is that correct? Pixel movement also seems preferable over path movement so that the hero can be moved just a couple pixels out of the way of the NPC instead of multiples of 8 pixels.

So I got something setup to move the hero when an NPC walks into him, but now I'm running into problems with making sure the hero doesn't get pushed into an obstacle when nudged. As an example, consider an NPCs walking along a path in the North direction with the Hero to the North of the NPC. When a collision occurs, I want to nudge the hero to the NW because if I only nudge the hero N, then the NPC could end up pushing the hero for the entire length of the path.

To nudge the hero to the NW, I give the hero's pixel movement a trajectory with several entries of {-1, -1}. The problem now is if there is an obstruction on the map to the west of the hero, I still want the hero to be moved to the N. It seems the hero's movement just calls on_obstacle_reached() and doesn't move the hero at all, even though there is no obstacle to the North.

The workaround I then used for the above problem is to give a trajectory that only moves one pixel W then one pixel N, alternating (i.e. {{-1,0}, {0,-1}, {-1,0}, {0,-1}...etc.}). This actually works for the most part, but there are still a few corner cases that don't quite work.

See the example image below, where the green 16x16 box is the hero, the blue is the npc, who is walking to the north to the doorway in the building above. The grey pixels (and the doorway) are traversable. So then the first time the NPC and hero bounding boxes overlap, there are six pixels (cyan) where the overlap occurs. Now obviously nudging the hero to the north fails because there is a building in the way, but nudging the hero to the east also fails because if the hero is moved 1 pixel to the east, the hero still overlaps the NPC by 5 pixels.

I don't have a good solution to this problem. The only thing I can think of is to do set_ignore_obstacles(true) for the hero and do my own manual obstacle detection, but that's tricky because it runs the risk of pushing the hero into the side of a building and getting stuck. I'm assuming I'd have to use map:get_ground() to do my own collision text, but how does that work? With a "wall_top_right" tile, for example, the bottom left corner of the tile is traversable and the top right corner is not. So does that mean that a coordinate in the top right half of the tile returns "wall_top_right" whereas a coordinate in the bottom left half of the tile returns "traversable"?

Or does anyone have any better ideas?

[Diarandor]

The quickest solution is just making the NPCs traversable (use custom entities as NPCs if necessary).

Another solution is making NPCs traversable, for the hero, during their movements. When they stop moving, you can make them  to be a solid obstacle, unless the hero is overlapping them (in that case, wait with a timer until the hero stops overlapping the NPC).

You should not try to push the hero because that will not always work (and will give you more problems than solutions), for instance if the hero is in a corner and NPCs get in the way, there is no space to push the hero.

[Christopho]

Yes, npc:set_traversable(true) is the solution.

But what is the problem with obstacles in the first place? If I remember correctly, when an entity with a path movement encounters an obstacle, it is temporarily stopped and the movement continues normally when the route is cleared.

[llamazing]

But what is the problem with obstacles in the first place? If I remember correctly, when an entity with a path movement encounters an obstacle, it is temporarily stopped and the movement continues normally when the route is cleared.

I'm wanting to do something similar to Majora's Mask where NPCs follow precise routes at different times of the day. So at a certain time the NPC will be in an exact spot. If the NPC were to stop temporarily because the player got in their way, then not only would the NPC be delayed in getting to their destination, but there would also be discontinuities in the NPC's movements as the player transitions between maps.

This also means that when the player enters a map, the map script has to calculate where the NPCs are supposed to be depending on what time it is. This turned out to be not as difficult as I thought it would be, and I have code to do this that has been working well.

Another solution is making NPCs traversable, for the hero, during their movements. When they stop moving, you can make them  to be a solid obstacle, unless the hero is overlapping them (in that case, wait with a timer until the hero stops overlapping the NPC).

I think this solution will work for me. Thanks!

I think I came up with a better solution than using a timer. Once the NPC stops its movement, I assign a function to hero:on_position_changed(), and then every time the hero moves I check if there's still overlap with the NPC. When the hero is not overlapping the NPC, I make the NPC non-traversable again and then set hero.on_position_changed to nil so that the function stops getting called every time the hero moves.

I'll improve the code so that it works with multiple NPCs moving around at the same time (and I'd have to modify it a bit if I ever want to use hero:on_position_changed() for something else), but here's example code for illustrative purposes:

Code (lua) Select Expand


--Code to begin an NPCs movement
local hero = game:get_hero() --this is not a map script, so hero needs to be defined

npc:set_enabled(true)
npc:set_traversable(true)

local mov = sol.movement.create"path"
mov:set_path(event.path)
mov:set_speed(16)
mov:set_ignore_obstacles(true)
mov:set_loop(false)

mov:start(npc, function()
--set npc back to non-traversable once player is no longer overlapping
hero.on_position_changed = function(self, x, y, layer)
if not self:overlaps(npc, "overlapping") then
npc:set_traversable(false)
hero.on_position_changed = nil
end
end

if npc_loc.facing then npc:get_sprite():set_direction(npc_loc.facing) end
end)


[Diarandor]

I think it is a very bad idea using hero.on_position_changed for this. If the hero changes map that code may give you problems. Also, that event may be used for other things and you may be overriding it. You should use a function of the NPC instead, because that is more natural and it is something related only to the NPC.

[Christopho]

The hero persists across maps so you have to be careful yes. Other remark: you forgot to declare your hero variable local.

But aside from that I think you have the right approach. I love majora's mask and its timed side quests

[llamazing]

I think it is a very bad idea using hero.on_position_changed for this. If the hero changes map that code may give you problems. Also, that event may be used for other things and you may be overriding it. You should use a function of the NPC instead, because that is more natural and it is something related only to the NPC.

Ah, you're right. I was thinking that the code associated with the hero would get wiped out on map transitions like it does for other entities. Since the hero persists outside of an individual map it could be problematic. I could use map:on_finished() to tidy things up on map transitions, but that would most likely become too complicated.

I don't think that there's a function of the NPC I can use since I only want to check for overlapping anytime that the player moves, and the NPC would be stationary.

I don't like the idea of using a timer, but it's probably what I'll end up doing.

Other remark: you forgot to declare your hero variable local.

Good catch! Fixed.

[llamazing]

I changed the implementation to use a repeating timer. In case anyone is interested, here's the revised code:

Code (lua) Select Expand

npc:set_enabled(true) --always enable when giving movement (overrides above)
npc.is_sleeping = nil --no sleepwalking!
npc:set_traversable(true)

local mov = sol.movement.create"path"
mov:set_path(event.path)
mov:set_speed(16)
mov:set_ignore_obstacles(true)
mov:set_loop(false)

mov:start(npc)
function mov:on_finished()
collision_check(npc)
if event.end_facing then npc:get_sprite():set_direction(event.end_facing) end
end

And here is the function collision_check():

Code (lua) Select Expand


--// Checks if entity1 & entity2 are overlapping and if not makes entity1 non-traversable
--// If they are overlapping then starts a timer to re-test again later (indefinite loop)
--if entity2 is not specified then the hero is used
local function collision_check(entity1, entity2)
if not entity2 then entity2 = game:get_hero() end
if not entity1 or not entity2 then return end

local do_check
do_check = function() --tests if entities overlap
if entity2:overlaps(entity1, "overlapping") then
sol.timer.start(entity1, 200, do_check)
else entity1:set_traversable(false) end
end

do_check() --kick off for first time
end

If you are wondering why I changed from using the movement callback function to using the on_finished() event, it's because sometimes I stop the movement a little early to get the NPC to line up with the next segment when the timing is slightly off. When I was stopping the movement early, the callback wasn't getting called. Now I can just call on_finished() manually whenever I stop the movement.

[llamazing]

FYI-- I've come across a bug with the code I posted for the timer implementation.

Description of the bug:

• Say an npc is assigned a path movement. The movement starts and the NPC is set to traversable.
• Now the hero waits stationary at the location on the map where the NPC will stop its movement.
• When the npc movement ends, since the hero overlaps the npc, the repeating timer begins and periodically checks if the hero is still overlapping the npc, and if not then makes the npc non-traversable.
• While the timer loop is still active, the npc is given a new movement path and set to traversable (even though it already is traversable).
• The hero can follow along with the npc since it is traversable. Note that the original timer is still looping.
• As soon as the hero moves away from the npc, the timer will end and make the (currently in motion) npc non-traversable.
• Now if the hero moves to where the npc's second movement ends, the hero will get stuck.

My solution is to assign an empty table to the npc entity when the timer is started. Whenever the npc is given a movement, I remove that table from the npc. The timer will only restart as long as that table is present. If a second timer were to be started while the first is still active, then the npc would get assigned a new empty table, and since the new empty table is a different instance than the original, the first timer would stop looping while the second timer continues to loop.

Here is the revised code (line 3 is new):

Code (lua) Select Expand

npc:set_enabled(true) --always enable when giving movement (overrides above)
npc.is_sleeping = nil --no sleepwalking!
npc.collision_check_context = nil
npc:set_traversable(true)

local mov = sol.movement.create"path"
mov:set_path(event.path)
mov:set_speed(16)
mov:set_ignore_obstacles(true)
mov:set_loop(false)

mov:start(npc)
function mov:on_finished()
collision_check(npc)
if event.end_facing then npc:get_sprite():set_direction(event.end_facing) end
end

And the revised collision_check() function (lines 8-10,14 & 18 are new):

Code (lua) Select Expand


--// Checks if entity1 & entity2 are overlapping and if not makes entity1 non-traversable
--// If they are overlapping then starts a timer to re-test again later (indefinite loop)
--if entity2 is not specified then the hero is used
local function collision_check(entity1, entity2)
if not entity2 then entity2 = game:get_hero() end
if not entity1 or not entity2 then return end

--only restart the timer while the context remains unchanged
local context = {} --newly created empty table is unique identifier
entity1.collision_check_context = context --replaces previous context

local do_check
do_check = function() --tests if entities overlap
if entity1.collision_check_context==context then
if entity2:overlaps(entity1, "overlapping") then
sol.timer.start(entity1, 200, do_check)
else entity1:set_traversable(false) end
end
end

do_check() --kick off for first time
end

[Christopho]

You can store the timer and cancel it explicitly.

[llamazing]

You can store the timer and cancel it explicitly.

I didn't think that would work because there isn't just one timer. The timer expires and generates a new timer, so the stored reference to the original timer would have to be updated with the new timer each time. And then I wasn't sure if there could be a race condition where two different sets of timers running simultaneously would both be vying to overwrite the same variable at the same time.

I don't know, my method seemed cleaner and safer.

[Christopho]

Keeping several timers running simultaneously is a (small and temporary) memory leak. If I understand your code correctly, you make sure that previous timers have no effect anymore but they still exist and run, which is a waste of resource.
You can cancel the previous timer properly with timer:stop() when there is one.

Code Select Expand


local function do_check()
   ...
end

if my_entity.collision_timer ~= nil then
  my_entity.collision_timer:stop()
end
my_entity.collision_timer = sol.timer.start(my_entity, do_check)


Also, in your timer function, don't forget that you can return true if you want the timer to be repeated.

[llamazing]

Also, in your timer function, don't forget that you can return true if you want the timer to be repeated.

Ah yes, I did forget that timers can be repeated by returning true. That makes for a cleaner implementation; I like it. In fact, I'm going to have to go back and apply that to some of my other scripts that use timers as well.