Issues with pathfinding on unwalkable nodes.
Closed this issue · 10 comments
Hi there @collinhover !
I know that you are working currently on the problems i mentioned on issue #112. So i feel a little bit shabby to bring a new topic on, but right now i am struggling with an pathfinding issue that prevents me to make any progress on my game.
I am working on an old school point and click adventure. I rebuild a simplified version of the famous SCUMM interface. But i can't interact with items "at the wall" because my collision tiles, made for preventing the player going up the wall, are making pathfinding impossible.
Sounds confusing? Example:
The player points at a book located on top of a bookshelf. He can select a command like "walk to book" or "pick up book", the player moves to the desired location and triggers the interaction (no collision needed, he just needs be near the object). But because the book is not at a walkable node, the pathfinding method will return an empty array, the moveTo method will not move the player and the interaction won't be possible.
I made some pictures to illustrate some workarounds i tried:
I pushed the collision box via offset to the feet of the player. Wherever i click, the player will move exactly at that location (respectively position his feet at that position - what is intended). But the collision tiles, that prevent the player from walking up the wall, will also prevent an interaction with the chest (dumb placeholder art in this case, chests don't float usually) or with an item higher than that (e.g a clock).
So making the collision box of the player bigger seemed to be a good idea! Now i can move the player via pathfinding to objects at the wall and interaction is possible. Making the collsion tiles a little bit higher still prevents the player from going up the wall as well.
However normal walking will not be possible anymore. Everytime the player moves via pathfinding, the pathfinding will get a different "reference point" for calculating (sometimes from the feet, sometimes from the head) resulting in a "demonic twister animation" inspired by Taz from the looney toons. On top of that, a collision box so big makes naviagtion through a room with obstacles very difficult.
Next idea: Shifting the collision box up. No demonic animations while using pathfinding anymore! Interaction with items on the wall is possible! But clicking anywhere, the player will position itself at that location with his head, and not his feet anymore. Looks and feels very awkward. Additionally the player can walk "outside the level", which you can see here:
So all of my workarounds failed hard, or had some major disadvantages :O
I think the best solution would be shifting the box to the feet (first picture) and modify the pathfinding. It would be sooo awesome if the pathfinding could return the nearest walkable node of the target, if the selected node is not walkable! So clicking on the chest on the first picture would move the player directly beneath the chest.
However, an option for this behavior is not built in, am i right? I started to mess around with the getPathTo method of the pathfinding.js file. But to be honest ... i don't understand much of the code at that method.
Do you have any idea, an advice or suggestions, how i could achive that needed behavior? If i had a clue how to solve this via modifying the getPathTo method, i would add a new config property, and just trigger that mechanic when that property is set to true.
I think all games with point and click controls could benefit from that in some situations.
Some examples:
- The Player is at a beach. Clicking on the sea/lake would move him at the end of a pier.
- The Player is inside a prison cell. Clicking on the prison bars will move him there.
- The Player is on a pirate ship, which tries to board another ship. Clicking outside the pirateship would position the player at the edge of hiw own ship, triggering some transition.
I don't take your support for granted. Thank you for any help, tips and thoughts on this topic! I am pretty stuck right now :-/
Update: Checking for the neighbors of the node (pathfinding.js --> getPathTo method --> line 1063) will move the player beneath the chest (first picture)! So far so good!
if( currentNode === destinationNode
|| currentNode === destinationNode.neighbors[0]
|| currentNode === destinationNode.neighbors[1] ) {
while( currentNode ) {
path.push( currentNode );
currentNode = currentNode.prevNode;
}
_cleanup();
return path;
}Needless to say that this will just work in this case. But for my other examples (beach, prison, pirateship), or items higher than the chest in the first picture, it won't work because the neighbor nodes of the destinationNode are not walkable, right? So i have to iterate through all of the neighbors and the neighbors of that neighbors (and so on) until i hit the currentNode ... right?
I am still confused .. but i hope that i am on the right way.
The major problem I see here is that you're wanting certain tiles to appear walkable but still collide as usual. We can't have the pathfinding ignore collision tiles universally, because then pathfinding becomes useless. However, you just want tiles on the border of the level to be walkable, right?
Pathfinding maps! Paint some green over the collision tiles you want the pathfinding system to treat as walkable, and you should have what you're looking for. It has been a while since I've reviewed that code, but if this doesn't work, it will be very easy for me to modify the pathfinding code to work with this. Can you test it and let me know?
On a side note, the reason your character is going nuts with pathfinding when you change his collision box to his entire body size is that he has no gravity. Characters with gravity always pathfind from their feet, but characters without gravity are assumed to be top-down so they pathfind from any side.
Painting some green pathfinding maps over the collison tiles won't do anything right now. So if you could modify the pathfinding code ... that would be soooo awesome! Thanks in advance for your help!
Again, sorry for the delay. Can you try the latest dev? I've set it so that the two green and one yellow/orange tile will force a node to be walkable, even if a collision tile is there. I'm not entirely sure how this will affect pathfinding. Let me know how it works for you.
Hi @collinhover,
first of all, you don't have to apologize for the delay, or for any mistakes/bugs mentioned on other issues! I tried some other HTML5/JavaScript-Engines, but sticked with ImpactJS. But Impact just provides me with the very basics, everything else had to be done from the scratch. That was pretty time consuming and sometimes frustrating.
Impact++ makes everything better. With ++ it now feels like a much more complete engine. On top of that you are very supportive here at Github and at the ImpactJS forum. So thank you for ++ and for all of your help!
Back to topic: It works! Exactly how i need it. Great job @collinhover! There is only one minor problem, while the character walks along the wall he changes his facing from time to time. Here is a video that shows the behavior:
http://www.youtube.com/watch?v=goz1CtYgslc&feature=youtu.be
Surely that behavior is triggered, because he wants to walk to that node up in that brief moment. Do you think you could add a fix to this? That would be great!
By the way, as far as i can tell pathfinding works like it should on all other situations.
My guess is that you've added walkable nodes on all the wall spaces? This is going to force the player to try to walk up into them, and when walking up they will try to face up. This seems like the proper behavior in most cases. For your special case, a simple fix for what is happening in the video might be to only add a walkable node right on top of the chest. Have you tried that?
Also, when you force the chest tile to be walkable, you might also force all the tiles above it and to the left and right to be unwalkable by using either the red pathfinding map tile or padding it with solid collision tiles. This way, the pathfinding can't find paths outside of the map like it is doing in the video. Or do you want that behavior?
I stopped working on this part of my game, since i heared nothing from you for about 2 weeks, before you responded to me on the 23rd. And exactly on this day, i started my vacation. So sorry for my late anwser to your suggestion!
Back to topic: It works! Painting the tiles like you suggested fixed my Issue with the facing direction! Great! Thank you :D
Good to hear =) sorry for the slow replies, been really busy lately.