[mod] New Pathfinder [wip][pathfinder]

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

Sokomine wrote: The question of weather a door is open or closed cannot be determined that easily. Doors might have been placed and stored either in closed or opened state - whatever was more convenient for the builder. While doors can still somehow be analyzed, trapdoors/hatches are very nasty and are not really handled by my modifications yet.
Doors have no closed or open state. My code analyse param2 and the moving direction and until now I haven't found any issues with this method

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

TumeniNodes wrote:burli, that only makes sense to me.
Leave handling doors to each mob. It makes sense because, some mobs simply should not be able to open doors, etc..
The player needs to be able to be safe (or just be able to get away from mobs)in some places (on the other side of doors).
And it would look strange if animals trying to walk through closed doors. I'm really happy that I solved this because at the first moment I thought it is not possible. The only problem is, that an open door takes some space and mobs may stuck if they are to wide. And it will be difficult to check if a double door is open

ShadMOrdre
Member
Posts: 1118
Joined: Mon Dec 29, 2014 08:07
Location: USA

Re: [mod] New Pathfinder [wip][pathfinder]

by ShadMOrdre » Post

Here's a simple logic solution for mob code.

Assume target is within four walls with one or multiple doors, and mob is outside.

1. Search path to target.
2. If target path = true then walk path.
3. If path false, search for temporal node, ie a door, hatch, or fencegate
4. If temporal node found, then path to tempnode.
5. Mob code to handle tempnode.
6. Goto line 1.

Can't be hard to code, and IS responsibility of intelligent agent, a mob in this case. For mobs that shouldn't handle doors, simply end mob pathfinding at step 4.

Maybe pthfinder code can return 1 of 3 values,
1. Path to target
2. Path to nearest position
3. No path available.

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

ShadMOrdre wrote: Assume target is within four walls with one or multiple doors, and mob is outside.

1. Search path to target.
2. If target path = true then walk path.
3. If path false, search for temporal node, ie a door, hatch, or fencegate
4. If temporal node found, then path to tempnode.

Can't be hard to code
Well, but this doesn't work if doors are just "transparent". A pathfinder can't determine if a path is valid, if he ignores closed doors. He will always find the shortest path, and this will be in most cases through the closed door. You can't say "The last path is invalid, find another one". To detect if a door is open or closed is the best solution

I will add a function that detects fences and walls. Mobs with a jump height of 1 shoudn't jump over fences and walls.

Vertical movement like climbing a ladder is more difficult. A* is not made for 3d movement

bell07
Member
Posts: 604
Joined: Sun Sep 04, 2016 15:15
GitHub: bell07

Re: [mod] New Pathfinder [wip][pathfinder]

by bell07 » Post

THe path calculator should be able to accept custom "passable" node-types defined by mod. By default they are airlike nodes only. If a mob (like NPC) can open doors, the "door" can be added to the list so the path calculates the path trough doors and the mob needs to handle the open and close action.
If an mob can pass stairs, the "stair" can be added to the list. The same for "ladders" as axample.

Of course each custom "passable node-type" needs an own implementation because of no generic solution. Stairs needs to be considered in other way as doors or ladders.

ShadMOrdre
Member
Posts: 1118
Joined: Mon Dec 29, 2014 08:07
Location: USA

Re: [mod] New Pathfinder [wip][pathfinder]

by ShadMOrdre » Post

burli,

For pathfinding code, simply treat all closed doors as a barrier, like any other wall . It is up to agent to figure out its problem, ie, a closed door, wall, stairs, or ladder.. In 2d, agent still gets shortest path to target, and because target is at different elevation, agent must search for stairs, ladder, and so forth. This falls on agent to figure out. Gates and doors are, and should be barrier. Portals on other hand are direct paths, so if you accommodate anything , add code for that, but again, because this is onus of agent, I would recommend against even accommodating portals. A path is simply a path. Agent must determine independently if path is valid, good, or otherwise.If you weight nodes in area, using smallest sum to find path to target, all nodes beyond barrier should get ruled out, rendering path to nearest in process.

Essentially, agent gets path to target or first obstacle. After handling obstacle, get path to target or next obstacle, until target is reached. This is why I recommend keeping pathfinder ignorant of obstacles.

In my pathfind algorythm, based on dykstra, I take only current node and neighbors into consideration.

1. Get neighbors of current node. If usable add to list of possible paths along with step count, meaning all nodes checked during this iteration get same step count assigned
2. For each usable, do same, minus node just exited and nodes already marked usable.
3. Shortest path equals straight line, so if beyond a threshhold, pathfinder stops search.
4. Once pathfinder stop search, simply take nearest pos to target with lowest step count, simply by backtracking path to origin, nullifying all other previously marked nodes.

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

bell07 wrote:THe path calculator should be able to accept custom "passable" node-types defined by mod. By default they are airlike nodes only. If a mob (like NPC) can open doors, the "door" can be added to the list so the path calculates the path trough doors and the mob needs to handle the open and close action.
If an mob can pass stairs, the "stair" can be added to the list. The same for "ladders" as axample.
Custom nodes are the wrong way. The mob tells the pathfinder if he can climb, jump, swim or whatever and the pathfinder should find a path based on this informations.

bell07
Member
Posts: 604
Joined: Sun Sep 04, 2016 15:15
GitHub: bell07

Re: [mod] New Pathfinder [wip][pathfinder]

by bell07 » Post

burli wrote:Custom nodes are the wrong way.
Fully agree. I do'nt meant custom nodes. I meant custom logic for some nodes in path finder (I called it node-types), that can be enabled for calculation. Like "Calculate path with doors are passable". I meant the same as
burli wrote:The mob tells the pathfinder if he can climb, jump, swim or whatever and the pathfinder should find a path based on this informations.

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

ShadMOrdre wrote:burli,

For pathfinding code, simply treat all closed doors as a barrier, like any other wall . It is up to agent to figure out its problem, ie, a closed door, wall, stairs, or ladder..
Sure, but the pathfinder must be able to detect if a door is open and should be able to find a path through an open door. Also he should be able to find a path based on the size of the mob. If the mob is to tall or wide for a door he should find another path
ShadMOrdre wrote: In 2d, agent still gets shortest path to target, and because target is at different elevation, agent must search for stairs, ladder, and so forth. This falls on agent to figure out.
Well, no. A mob doesn't know how to get to a target if the pathfinder doesn't tell him. My algorithm is able to jump or fall down based on jumpheight and fear of height. If the target is at a different elevation he can find a path, if it is possible. But he should also find a path using ladders, if a mob "can_climb". It would be much more complicated to search for ladders (with find_nodes_in_area() )and try to find the correct way. The pathfinder is the right place to find a path from start to target.
ShadMOrdre wrote:Essentially, agent gets path to target or first obstacle. After handling obstacle, get path to target or next obstacle, until target is reached. This is why I recommend keeping pathfinder ignorant of obstacles.

In my pathfind algorythm, based on dykstra, I take only current node and neighbors into consideration.

1. Get neighbors of current node. If usable add to list of possible paths along with step count, meaning all nodes checked during this iteration get same step count assigned
2. For each usable, do same, minus node just exited and nodes already marked usable.
3. Shortest path equals straight line, so if beyond a threshhold, pathfinder stops search.
4. Once pathfinder stop search, simply take nearest pos to target with lowest step count, simply by backtracking path to origin, nullifying all other previously marked nodes.
Maybe you missed that I already have written a working pathfinder based on A*.

ShadMOrdre
Member
Posts: 1118
Joined: Mon Dec 29, 2014 08:07
Location: USA

Re: [mod] New Pathfinder [wip][pathfinder]

by ShadMOrdre » Post

XD

Been following your progress for awhile. I only included my steps as FYI.

Agent knows target since agent chose target. Agent still has to have code to use door,ladder, gate....stairs being walkable already. Sending a full path means agent still has to handle obstacles . Pathfinder should not control agent. Or even provide list of obstacles. If pathfinder knows location of obstacle, path should stop there so agent can determine best course of action. Maybe taking ladder is shorter, but stairs and doors into room are safer. This is for agent to determine, not pathfinder...

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

ShadMOrdre wrote:XD

Been following your progress for awhile. I only included my steps as FYI.

Agent knows target since agent chose target. Agent still has to have code to use door,ladder, gate....stairs being walkable already. Sending a full path means agent still has to handle obstacles . Pathfinder should not control agent. Or even provide list of obstacles. If pathfinder knows location of obstacle, path should stop there so agent can determine best course of action. Maybe taking ladder is shorter, but stairs and doors into room are safer. This is for agent to determine, not pathfinder...
Agree. That's what I always say. Pathfinder should only find a path. They don't handle doors or whatever. The only "intelligence" in the pathfinder is to find a path for the mob based on some properties like jump height, size, can swim, can climb and so on.

A path can be an open door or trapdoor, a ladder, a lake... If the mob is able to use this path, the pathfinder should be able to find it, no more and no less. Everything else is up to the "intelligence" of the mob.

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

In this video I demonstrate how accurate my pathfinder works. He is able to find open doors, walk on stairs and find a path even in a dense forest.

Currently this only works with stepheight 1. To use real jumping I need one more node above the head of the mob or I need to reduce the height of the collision box. Also it was necessary to reduce the collision box from 0.8 to 0.7 or less because a mob can't pass doors or may stuck if he wants to drop down in a 1 by 1 hole and is rotated by 45° because the diagonal dimension is too big.

And now enjoy the short video.
https://youtu.be/QuqXuyg8PrE

bell07
Member
Posts: 604
Joined: Sun Sep 04, 2016 15:15
GitHub: bell07

Re: [mod] New Pathfinder [wip][pathfinder]

by bell07 » Post

WTF? Really Nice! Great Work!

Which mob-framework is used with your pathfinder?

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

There is no actual framework. I coded everything myself

User avatar
jas
Member
Posts: 593
Joined: Mon Jul 24, 2017 18:15
IRC: Freenode
Location: IRC

Re: [mod] New Pathfinder [wip][pathfinder]

by jas » Post

I'm testing on dcbl.duckdns.org with mobs_animal, mobs_monster, and goblins (and slimes). I changed the settings in mobs_redo/api.lua per your suggestions, for all registered mobs, to test. (I did notice a lot of printing to console, which I wonder if I should disable.)

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

In the current version I disabled some of the parameters for testing. I have fixed values for mob size and jump height/fear of height. The only used parameters are currently the start and end position.

Also the current version on github can't walk through doors with 2 node high mobs. I'll need to push the current one first.

And as I mentioned in the first post, this mod is just a proof of concept and even if it works well it might not be a good solution for games. It might work for singleplayer where only a few mobs are active at the same time, but on a server with 10 or more players it might become critical.

And of course you can disable each print() line

But thanks for the test. Maybe you can report how it works. Any feedback helps

User avatar
jas
Member
Posts: 593
Joined: Mon Jul 24, 2017 18:15
IRC: Freenode
Location: IRC

Re: [mod] New Pathfinder [wip][pathfinder]

by jas » Post

I'd previously disabled pathfinding for most/all mobs because I didn't like it, but wanted to give this a go. I'll let you know how things work out, but in the meantime I'm going to try to figure out why the zombies get caught up on default:grass_n plantlike nodes. And why the mobs seem to make a sound each time they change direction? (Maybe that's mobs_redo, not pathfinder.)

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

That's definitely mobs redo. The pathfinder ignores plantlike nodes and doesn't make sounds.

User avatar
jas
Member
Posts: 593
Joined: Mon Jul 24, 2017 18:15
IRC: Freenode
Location: IRC

Re: [mod] New Pathfinder [wip][pathfinder]

by jas » Post

Thanks. I see this is its own thing now; I asked even after I'd read the whole thread! Ha, it's a very interesting mod/project anyway. Best wishes!

User avatar
csirolli
Member
Posts: 133
Joined: Mon Jan 15, 2018 21:46
GitHub: HeyITGuyFixIt
IRC: CSirolli
In-game: CSirolli
Location: Florida, USA
Contact:

Re: [mod] New Pathfinder [wip][pathfinder]

by csirolli » Post

Any new development on this?

User avatar
burli
Member
Posts: 1643
Joined: Fri Apr 10, 2015 13:18

Re: [mod] New Pathfinder [wip][pathfinder]

by burli » Post

I don't know if it makes sense to continue the developement in lua. Would make more sense to port this to C++. But I can't do this. Is there any progress on this from the core devs?

Probably I will fix some bugs or add some new features in the near future, but sooner or later a C++ port is unavoidable

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: [mod] New Pathfinder [wip][pathfinder]

by Sokomine » Post

It would be great if the pathfinder could handle nodes like ladders and ropes, where climbing up and down or just walking through is possible. That's still something that might make it hard for mobs that want to build houses based on my handle_schematics/citybuilder mod as that spawns the building with scaffolding nodes that can be climbed. Ladders are also quite common in more medieval buildings.
A list of my mods can be found here.

User avatar
Wuzzy
Member
Posts: 4786
Joined: Mon Sep 24, 2012 15:01
GitHub: Wuzzy2
IRC: Wuzzy
In-game: Wuzzy
Contact:

Re: [mod] New Pathfinder [wip][pathfinder]

by Wuzzy » Post

I have now finally actually given your pathfinder a try. I tested it with my new test mod “testpathfinder” in the “DevToys” modpack to visualize the waypoints. It's very useful! But you need to modify the code first to replace minetest.find_path. viewtopic.php?f=9&t=23802
For testing, I also greatly increased the timeout.


And, I must say, your pathfinder works quite beautifully! It even supports the height clearance of 2 nodes, which is very important for many mobs! Wide mobs will still not work, obviously. But it's a start. Sorry for being so harsh previously. This is obviously a proof-of-concept and there's nothing wrong with that.
The returned path actually makes sense, unlike the very very broken A* search in core Minetest.

Unsurprisingly, your mod is rather slow. The A* search in Minetest regularily takes under 1ms, while your mod is usually in the 100s of milliseconds. Your mod is over 100 times slower than C++. I understand this is a proof-of-concept, but I just want to stress how important it is to have a functional C++ pathfinder.

I have found a bug: Sometimes, the pathfinder fails not with nil but by returning a single position.

One bug that is in both official and your pathfinder is that it ignores overhigh nodeboxes. It treats them as 1-node high boxes and jumpable.

Some general thoughts about pathfinding:

Ladders and liquids have been mentioned many times. I would recommend that all those advanced features should be optional. The pathfinder should mak not too many assumptions about the thing that wants to find its path. Not all mobs want or can climb ladders, or swim, etc. Being able to turn off certain pathfinding behaviors also gives more variety as well. =)

A difficult challenge I see with pathfinding for Minetest are nodeboxes. It's not always clear if you can walk through them or not and it also depends hugely on how large your collisionbox is. And what's worse, the orientation of the nodebox is important as well. The challenge is basically: Is a walkable nodebox passable for me or not? I see you have done something with doors but there really needs to be a generalized solution.

What is really important for a pathfinder would be able to exclude certain nodes from the pathfinding. This is important for mobs that need to walk around hazards like lava.


I think the Lua pathfinder should be explored a little further, especially to find out the solutions to the more “tricky” challenges.

User avatar
runs
Member
Posts: 3225
Joined: Sat Oct 27, 2018 08:32

Re: [mod] New Pathfinder [wip][pathfinder]

by runs » Post

This should be ported and replace the official one.

User avatar
Wuzzy
Member
Posts: 4786
Joined: Mon Sep 24, 2012 15:01
GitHub: Wuzzy2
IRC: Wuzzy
In-game: Wuzzy
Contact:

Re: [mod] New Pathfinder [wip][pathfinder]

by Wuzzy » Post

I'm still waiting for sorcerykid's pathfinder to appear.

Post Reply

Who is online

Users browsing this forum: No registered users and 17 guests