How to prevent NPCs from overlapping?

Ask and answer questions about making games and related topics. Unrelated topics go in that other forum.

Moderators: marionline, SDHawk

User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

How to prevent NPCs from overlapping?

Post by sheamkennedy »

I'm attempting to make a puzzle. The puzzle requires you to get from the left side of a room to the right side. The challenge is that there are NPCs that mirror your movement and block your path. The only way to reach the other side is to offset the NPCs by making them run into walls when they try to mirror your movement.

I have a script that is mostly working the way I want. When the hero is walking the autorun loop will call a script which moves all the NPCs on the map in the hero's mirrored direction.

The problem is that sometime the NPCs are overlapping (occupying the same space). I don't want this to happen. If the space is already occupied by an NPC that can't move then no other NPC should be able to walk on to it. I'm not sure why this happens. My NPCs are set to "use" so they should not be able to step on each other. I've included a .gif to show the behaviour.

Here's my scripts so far:

Code: Select all

plotscript, Map Auto Run 0, begin

  while(1 == 1) do(
    if(check tag(3) == off) then(
		if(hero is walking(me) == true) then(
		  set tag(3, on)
		  suspend player
		  # Perform all movements/actions
		  mirrorNPC 1
	  
		  resume player
		  set tag(3, off)
		)
    )
  wait
  )
end

Code: Select all

script, mirrorNPC 1, begin
  variable(copy, whichNPC)
  for(copy, 0, 19) do(
    whichNPC := NPC reference (1, copy)
    if&#40;whichNPC <> 0&#41; then&#40;
	  #Get hero direction
		heroDir &#58;= hero direction&#40;0&#41;  
	  # Move NPCs in mirror direction
	  if&#40;heroDir == up&#41; then&#40; 
		mirrorHeroDir &#58;= up
	  &#41; else if&#40;heroDir == down&#41; then&#40;
		mirrorHeroDir &#58;= down
	  &#41; else if&#40;heroDir == left&#41; then&#40;
		mirrorHeroDir &#58;= right
	  &#41; else if&#40;heroDir == right&#41; then&#40; 
		mirrorHeroDir &#58;= left
	  &#41;     
	  show value&#40;mirrorHeroDir&#41;
	  if&#40;check NPC wall &#40;whichNPC, mirrorHeroDir&#41; == false&#41; then&#40;
        walk NPC&#40;whichNPC, mirrorHeroDir, 1&#41;
      &#41;
    &#41;    
  &#41; 
  for&#40;copy, 0, 19&#41; do&#40;
    whichNPC &#58;= NPC reference &#40;1, copy&#41;   
    if&#40;whichNPC <> 0&#41; then&#40;
      wait for npc&#40;whichNPC&#41; 
    &#41;  
  &#41;  
end
Attachments
A Mirror0010.gif
A Mirror0010.gif (325.21 KiB) Viewed 2832 times
Last edited by sheamkennedy on Thu Feb 15, 2018 1:10 pm, edited 2 times in total.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

I'm guessing you run the "suspend obstruction" command somewhere, such as the new game script. That allows NPCs to walk through each other. Alternatively, maybe you use "set npc obstructs"?

Note that "check NPC wall" only checks for possible collision with walls, not other NPCs. You could add "npc at spot" to that if-check to also check if there's already an NPC there.
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

TMC wrote:I'm guessing you run the "suspend obstruction" command somewhere, such as the new game script. That allows NPCs to walk through each other. Alternatively, maybe you use "set npc obstructs"?
I didn't run suspend obstruction anywhere in the game thus I was not expecting the NPCs to overlap like this but they still are for some reason... I think if I get to the bottom of that it'll solve my problem.
TMC wrote:Note that "check NPC wall" only checks for possible collision with walls, not other NPCs. You could add "npc at spot" to that if-check to also check if there's already an NPC there.
Okay, I'll get rid of the check NPC wall as that's not doing anything for me.

If I add "npc at spot" I think the effect I'm trying to achieve will fail because I want an NPC to always replace the spot of an adjacent NPC unless said adjacent NPC can't move due to a wall. For example if there is one npc with another npc to it's north, If their next move is north npc#1 should take the spot of npc#2. But if npc#2 is stuck against a wall or something then npc#1 should not take it's spot otherwise there will be an overlap. Another reason why this won't work is that the NPC's move based on a for-loop to cycle through each npc copy. If npc copy 0 is checked first and npc copy 1 is in it's way then npc copy 0 will not move even though it should in most cases.

So I think I'm still seeking a solution.

Just to clarify if the hero moves I want all the NPCs to mirror the hero's movement simultaneously (unless there is a wall or stuck NPC in their path of movement.
Last edited by sheamkennedy on Thu Feb 15, 2018 3:20 pm, edited 2 times in total.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
User avatar
Bob the Hamster
Lord of the Slimes
Posts: 7658
Joined: Tue Oct 16, 2007 2:34 pm
Location: Hamster Republic (Ontario Enclave)
Contact:

Post by Bob the Hamster »

So here is what I think is happening.

The NPC collision code takes into consideration whether or not the other NPC is moving.

So when an NPC is holding still, collision considers its actual position-- but when an NPC is trying to walk, then collision considers the tile where the NPC is trying to move to.

This is true even immediately after a "walk NPC" command when a movement is scheduled, but the NPC has not actually moved a pixel yet.

You are making the NPCs move with "walk NPC" in a loop, and depending on what order the NPC copies are numbered, the collision works right some of the time, but not other times.

I am trying to think if there is a way to fix this in the engine...

Perhaps applying the collision checking immediately when "walk NPC" happens is not a good approach, and the collision checking has to be delayed until right before the movement happens.

I think changing this would definitely affect the way "walk NPC" and "NPC is walking" interact, which might be a back-compat problem, but I am not certain.

I'm trying to think what the easiest way to fix this in your script is-- short of disabling all the built-in collisions and manually checking all the wall and NPC collisions yourself like you might in a sidescroller.
User avatar
Bob the Hamster
Lord of the Slimes
Posts: 7658
Joined: Tue Oct 16, 2007 2:34 pm
Location: Hamster Republic (Ontario Enclave)
Contact:

Post by Bob the Hamster »

Actually, I am wrong about collision being checked immediately when "walk NPC" is executed.

I still think that the order of collision checking is a possible cause of this problem-- but maybe it will be easier to fix than I thought? Looking into NPC collision checking code now.

EDIT: After a little more testing, no I don't think this is NPC order-related, but I do still think it could possibly be an engine bug.

I was able to reproduce the bug pretty easily by copying your script and setting up a similar map
Last edited by Bob the Hamster on Thu Feb 15, 2018 5:17 pm, edited 2 times in total.
User avatar
Bob the Hamster
Lord of the Slimes
Posts: 7658
Joined: Tue Oct 16, 2007 2:34 pm
Location: Hamster Republic (Ontario Enclave)
Contact:

Post by Bob the Hamster »

Here is a pretty simple script that reproduces the same bug

Code: Select all

plotscript, Map Auto Run 0, begin
  
  walk npc&#40;1, up, 1&#41;
  walk npc&#40;2, up, 1&#41;
  walk npc&#40;3, up, 1&#41;

  wait for npc&#40;1&#41;
  wait for npc&#40;2&#41;
  wait for npc&#40;3&#41;

  walk npc&#40;1, up, 1&#41;
  walk npc&#40;2, up, 1&#41;
  walk npc&#40;3, up, 1&#41;

  wait for npc&#40;1&#41;
  wait for npc&#40;2&#41;
  wait for npc&#40;3&#41;

end
Image
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

Bob the Hamster wrote:Here is a pretty simple script that reproduces the same bug
Image
In the meantime should I keep coding and wait for a bug fix or is there a way to easily achieve the behaviour I want? I suppose I could plan my puzzles out on paper for now as i know how I want the NPCs to move.
Last edited by sheamkennedy on Fri Feb 16, 2018 12:56 am, edited 2 times in total.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

Oh wow, this is a real can of worms. This is going to be a very difficult bug to fix 100% properly! In fact I definitely wouldn't prioritise it. (I mean, we haven't even fixed that MIDI crash bug yet after a decade)

Because in your case the NPCs all move in the same direction it is actually feasible for you to script the NPC movement and collision checking yourself. When the NPC move left you need to loop over the NPCs starting from the leftmost and heading towards the right. That way, for ever NPC you move, you've already determined whether any NPC to its left will move or not. You check the tile to the left for a wall, the hero, or for an NPC which isn't going to move. You can use the "npc is walking" command to check the latter.


We need to fix this in such a way that the ability for NPCs standing in queue to all simultaneously advance isn't destroyed. Like this:
Image

Code: Select all

plotscript, dance, begin
        walk npc&#40;0, south, 1&#41;
        walk npc&#40;1, east, 1&#41;
        walk npc&#40;2, north, 1&#41;
        walk npc&#40;3, west, 1&#41;
end
Queues which loop on themselves like this is are a big extra complication to support.

For each NPC, we don't know whether it will move or not until after the same determination for all the other NPCs. So I think that we would need to do the NPC collision checking and movement using a depth-first search. When processing an NPC:
-check for collisions with everything except other NPCs (walls, zones, heroes). If there's a collision, stop the NPC's movement.
-then for every other NPC:
--if we've already determined whether that NPC will or won't move, we know where it's moving to, and can do the collision check with it
--if we haven't determined it yet, we need to recursely check it
--if we've already recursively checking this NPC (or on the deferred queue, see below), we should make the assumption that it will move, so that the "dance" script above works
--if there are multiple NPCs on the same tile, then we just need to check all of them, BUT this means that the above assumption can retroactively turn out to be false! We won't know if it's correct until all of the multiple NPCs on the tile have been checked, which is after some of recursive movement/collision calls have returned. Therefore, any such calls can't actually update the NPCs. Those NPCs need to go on a "deferred" queue to be advanced later.

After finishing that, for every NPC in the deferred queue, update its movement.

I don't think the above is totally correct.

And that's the easy part. The harder part is dealing with A*, which uses an cache of NPC locations, and all the places where NPC collision checks for a single NPC are performed. I'm thinking that changing how these work is going to be astronomically infeasible, and they will work fine as they are even if they give the wrong result, so they should stick to the old way of collision checking.

Add into that the fact that we want to rewrite movement checks anyway to fix the horribly broken checking for misaligned NPCs/heroes. And what about pixel-based movement?
Also, I'm suspicious of the fact that heroes and NPCs are treated completely separately. If I were writing it from scratch, I would certainly treat them all as walkabouts.
Last edited by TMC on Fri Feb 16, 2018 5:05 am, edited 3 times in total.
User avatar
Bob the Hamster
Lord of the Slimes
Posts: 7658
Joined: Tue Oct 16, 2007 2:34 pm
Location: Hamster Republic (Ontario Enclave)
Contact:

Post by Bob the Hamster »

Perhaps the easiest solution for now is to add a helper command for iterating over the NPCs in order by direction.
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

Bob the Hamster wrote:Because in your case the NPCs all move in the same direction it is actually feasible for you to script the NPC movement and collision checking yourself. When the NPC move left you need to loop over the NPCs starting from the leftmost and heading towards the right. That way, for ever NPC you move, you've already determined whether any NPC to its left will move or not. You check the tile to the left for a wall, the hero, or for an NPC which isn't going to move. You can use the "npc is walking" command to check the latter.
Okay I think I can do something like this. I'll keep playing around with this puzzle.
Bob the Hamster wrote:Perhaps the easiest solution for now is to add a helper command for iterating over the NPCs in order by direction.
Yes that would be useful. Then I could easily scan through all these NPCs in a simple way.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

Alright, so now I'm trying to make a script that scans from left to right and makes every NPC reference(1) mirror the hero movement. So far my script works for the first NPC being scanned but only moves that NPC not all of them like I'd expect. I must be doing something wrong but I'm just not seeing it. Here's the script which scans through my NPCs left to right:

Code: Select all

script, mirrorNPC 1, begin
  variable&#40;copy, whichNPC&#41;
  variable &#40;CurrX&#41; 
  variable &#40;CurrY&#41; 
  
  	  #Get hero direction
		heroDir &#58;= hero direction&#40;0&#41;  
	  # Move NPCs in mirror direction
	  if&#40;heroDir == up&#41; then&#40; 
		mirrorHeroDir &#58;= up
	  &#41; else if&#40;heroDir == down&#41; then&#40;
		mirrorHeroDir &#58;= down
	  &#41; else if&#40;heroDir == left&#41; then&#40;
		mirrorHeroDir &#58;= right
	  &#41; else if&#40;heroDir == right&#41; then&#40; 
		mirrorHeroDir &#58;= left
	  &#41;
  if&#40;mirrorHeroDir == left&#41; then&#40;
    # Scan left-to-right
    for &#40;CurrX,0,MapWidth,1&#41; do &#40;
      for &#40;CurrY,0,MapHeight,1&#41; do &#40;
        whichNPC &#58;= NPC at spot&#40;CurrX, CurrY&#41;
        if&#40;whichNPC == NPC reference&#40;1&#41;&#41; then&#40;
          if&#40;check NPC wall &#40;whichNPC, left&#41; == false&#41; then&#40;
            if&#40;NPC at spot&#40;CurrX--1, CurrY&#41; == true&#41; then&#40;
              if&#40;NPC is walking &#40;NPC at spot&#40;CurrX--1, CurrY&#41;&#41; == true&#41; then&#40;
                walk NPC&#40;whichNPC, mirrorHeroDir, 1&#41;
              &#41;    
            &#41; else &#40;
              walk NPC&#40;whichNPC, mirrorHeroDir, 1&#41;
            &#41;
          &#41;    
        &#41;
      &#41;
    &#41;
  &#41;
  
  for&#40;copy, 0, 19&#41; do&#40;
    whichNPC &#58;= NPC reference &#40;1, copy&#41;   
    if&#40;whichNPC <> false&#41; then&#40;
      wait for npc&#40;whichNPC&#41; 
    &#41;  
  &#41; 
end
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

To iterate NPCs with directional preference, just use the "sort children" script command. It doesn't matter that you're changing the order of the slices, because the engine will re-sort them when they're drawn.

In the following, I'm assuming you have NPC/Hero layering set to "together"

Code: Select all

plotscript, mirror npcs, begin
  variable&#40;walkabouts, sl&#41;
  walkabouts &#58;= lookup slice&#40;sl&#58;walkabout layer&#41;

  sl &#58;= first child&#40;walkabouts&#41;
  while &#40;sl&#41; do &#40;
    switch&#40;hero direction&#40;0&#41;&#41; do &#40;
      case&#40;up&#41;    set sort order&#40;sl, slice y&#40;sl&#41;&#41;
      case&#40;down&#41;  set sort order&#40;sl, -1 *  slice y&#40;sl&#41;&#41;
      case&#40;left&#41;  set sort order&#40;sl, slice x&#40;sl&#41;&#41;
      case&#40;right&#41; set sort order&#40;sl, -1 *  slice x&#40;sl&#41;&#41;
    &#41;
    sl &#58;= next sibling&#40;sl&#41;
  &#41;
  sort children&#40;walkabouts&#41;

  # Now can iterate over npcs
  sl &#58;= first child&#40;walkabouts&#41;
  while &#40;sl&#41; do &#40;
    variable&#40;npc&#41;
    npc &#58;= npc reference from slice&#40;sl&#41;
    # This slice might actually be a hero slice, ignore those
    if &#40;npc <> 0&#41; then &#40;

      # ADD CODE HERE

    &#41;
    sl &#58;= next sibling&#40;sl&#41;
  &#41;
end
Also, "NPC at spot(CurrX--1, CurrY) == true" is wrong, that command doesn't return true/false. You should remove the "== true". Also a mistake on the next line: any NPC you find is an obstacle only if it's NOT walking. For example (adding two helper scripts, which allows using the same code for all four directions):

Code: Select all

script, dir X, dir, begin
  switch &#40;dir&#41; do &#40;
    case &#40;up, down&#41; do &#40;return &#40;0&#41;&#41;
    case &#40;right&#41; do &#40;return &#40;1&#41;&#41;
    case &#40;left&#41; do &#40;return &#40;-1&#41;&#41;
  &#41;
end

script, dir Y, dir, begin
  switch &#40;dir&#41; do &#40;
    case &#40;left, right&#41; do &#40;return &#40;0&#41;&#41;
    case &#40;down&#41; do &#40;return &#40;1&#41;&#41;
    case &#40;up&#41; do &#40;return &#40;-1&#41;&#41;
  &#41;
end

...
    x &#58;= npc X&#40;npc&#41; + dir X&#40;mirrorHeroDir&#41;
    y &#58;= npc Y&#40;npc&#41; + dir Y&#40;mirrorHeroDir&#41;
    blocking npc &#58;= NPC at spot&#40;x, y&#41;
    if&#40;blocking npc&#41; then&#40;
      if&#40;NPC is walking &#40;blocking npc&#41; == false&#41; then&#40;
...
Also, can't you use "wait for all" at the end?
Last edited by TMC on Fri Feb 16, 2018 7:56 am, edited 3 times in total.
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

@TMC:
Okay I've made all the changes but can't compile because "npc reference from slice(sl)" isn't recognized. It's not in the dictionary so I think this must be a homemade script of yours?
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

That's a new command in Etheldreme. You're behind the times!
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

TMC wrote:That's a new command in Etheldreme. You're behind the times!
Oh thats right I forgot to update! I'll get that right now, Thanks!
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
Post Reply