[mod] New Pathfinder [wip][pathfinder]

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

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

by burli » Mon Dec 04, 2017 06:38

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: 1641
Joined: Fri Apr 10, 2015 13:18

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

by burli » Mon Dec 04, 2017 07:56

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: 534
Joined: Mon Dec 29, 2014 08:07
Location: USA
GitHub: ShadMOrdre
In-game: shadmordre

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

by ShadMOrdre » Mon Dec 04, 2017 08:02

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.
MY MODS: lib_ecology lib_materials lib_clouds lib_node_shapes ---- Inspired By: Open Source Virtual World Simulator Opensimulator.
 

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

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

by burli » Mon Dec 04, 2017 08:53

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: 574
Joined: Sun Sep 04, 2016 15:15
GitHub: bell07

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

by bell07 » Mon Dec 04, 2017 09:36

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: 534
Joined: Mon Dec 29, 2014 08:07
Location: USA
GitHub: ShadMOrdre
In-game: shadmordre

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

by ShadMOrdre » Mon Dec 04, 2017 09:58

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.
MY MODS: lib_ecology lib_materials lib_clouds lib_node_shapes ---- Inspired By: Open Source Virtual World Simulator Opensimulator.
 

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

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

by burli » Mon Dec 04, 2017 11:27

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: 574
Joined: Sun Sep 04, 2016 15:15
GitHub: bell07

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

by bell07 » Mon Dec 04, 2017 11:48

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: 1641
Joined: Fri Apr 10, 2015 13:18

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

by burli » Mon Dec 04, 2017 11:52

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: 534
Joined: Mon Dec 29, 2014 08:07
Location: USA
GitHub: ShadMOrdre
In-game: shadmordre

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

by ShadMOrdre » Mon Dec 04, 2017 12:12

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...
MY MODS: lib_ecology lib_materials lib_clouds lib_node_shapes ---- Inspired By: Open Source Virtual World Simulator Opensimulator.
 

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

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

by burli » Mon Dec 04, 2017 12:31

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: 1641
Joined: Fri Apr 10, 2015 13:18

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

by burli » Wed Dec 06, 2017 08:26

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: 574
Joined: Sun Sep 04, 2016 15:15
GitHub: bell07

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

by bell07 » Wed Dec 06, 2017 09:31

WTF? Really Nice! Great Work!

Which mob-framework is used with your pathfinder?
 

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

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

by burli » Wed Dec 06, 2017 09:32

There is no actual framework. I coded everything myself
 

User avatar
jas
Member
 
Posts: 464
Joined: Mon Jul 24, 2017 18:15
GitHub: jastevenson303
IRC: jas_
In-game: jas

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

by jas » Wed Dec 06, 2017 11:09

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.)
2019-10-14 09:12:51: ACTION[Server]: jas activates
 

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

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

by burli » Wed Dec 06, 2017 11:46

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: 464
Joined: Mon Jul 24, 2017 18:15
GitHub: jastevenson303
IRC: jas_
In-game: jas

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

by jas » Wed Dec 06, 2017 13:17

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.)
2019-10-14 09:12:51: ACTION[Server]: jas activates
 

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

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

by burli » Wed Dec 06, 2017 13:24

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

User avatar
jas
Member
 
Posts: 464
Joined: Mon Jul 24, 2017 18:15
GitHub: jastevenson303
IRC: jas_
In-game: jas

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

by jas » Wed Dec 06, 2017 16:22

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!
2019-10-14 09:12:51: ACTION[Server]: jas activates
 

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

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

by csirolli » Fri Jun 22, 2018 06:06

Any new development on this?
Jesus is the only Way to heaven, the only saving Truth, and the only Life that is worth living.
 

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

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

by burli » Sat Sep 15, 2018 16:34

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: 3886
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine

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

by Sokomine » Wed Jan 02, 2019 19:51

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.
 

Previous

Return to WIP Mods



Who is online

Users browsing this forum: No registered users and 4 guests