EasyFinding – pathfinding

Hello,



i just made pathfinding. its in early stage, but i hope it will be better :slight_smile:



http://desmond.imageshack.us/Himg193/scaled.php?server=193&filename=screen2na.png&res=medium



https://code.google.com/p/easyfinding/



testcase contained



it is in early stage(i dont tested everything and it need improvments).



usage:

http://code.google.com/p/easyfinding/wiki/Usage



partial executing:

http://code.google.com/p/easyfinding/wiki/PartialExecuting



WaypointsNotFoundException is appeared if there is no way to get into destination

5 Likes

Don’t you have some example level where you can make a video so to visualize how it works?

speaking about classes it’s rather difficult for me to visualize the overall structure.

Are you using some kind of matrix to map the cells of the level?

1 Like

yes i use mapping by matrix(it is mapped by precision and using int values), but to save memory usage i dont hold neutral points in memory.



And yes, you have right, i will prepare a video, give me some time

1 Like

And this is not based on any existing codebase?



You ought to get in touch with @geniodella and @sploreg as they have been discussing pathfinding improvements recently.

1 Like

What routine are you using to calculate the waypoints?

1 Like
@erlend_sh said:
And this is not based on any existing codebase?

You ought to get in touch with @geniodella and @sploreg as they have been discussing pathfinding improvements recently.


its my 3d solution based on 2d array solution. My priority was to give ability of climbing/multifloor(multilayer) calculating. I dont looked into all other pathfindings. The Main calculation is slow for long distances. I think if someone of them is interested, then they will contact :)

For myself it work great, becouse for NPC server it use blindMove solution to make pathfinding faster(becouse it need to be fast for 1000 or more of npc's).

So i think it is perfect for strategy games, or rpg like UFO series
But it is bad solution for FPS games(becouse here usually we dont need to use multifloor pathfinding)

@Sploreg said:
What routine are you using to calculate the waypoints?


first routine is to set valueMap:
starting from start vector
while point in queue:
for all points(which was not visited, is not blockade and is moveable) arround this point set value to parent value+1 and add to queue
when last vector encounter, stop calculating

second routine is to collect path:
set actual vector as end vector:
1: from actual vector
2: seek point having actual vector value-1, if it find, then add actual vector to waypoints list and recusrive (1) for this new vector
when last vector encounter, stop calculating

on my laptop with standard VM config it have done work in 40 ms for distance ~20 float

the more distance the longer it is executing, like log(o)

but i have added BlindMove solution too, so if it is set on, then it try to make steps in end vector direction. if blockage appeared then first algoritm is executing

The actual solution in development is based on a navigation mesh,

are you using somekind of navigation mesh to prune the parts of the level that

are not walkable?

1 Like

It dont use jme NavigationMesh(i dont know if it work for multilevels), should it?



Algoritm work with some precision, for example 1f(1 meter). There are 3 types of point:

[java]public enum PointEntity {

BLOCKADE, MOVEABLE, NEUTRAL

}

[/java]



blockade type override moveable and neutral. moveable override neutral. Neutral points are not stored in memory(it is just a free space). points for terrain dont use additional memory becouse it use terrain.getHeight method. Geometries use additional memory due to contain blockade and moveable points





[java]easyFind.initGridFromWorld(rootNode);[/java]



here it check all SubNodes, Geometries and TerrainQuads.



For TerrainQuad it use class wrapper to use terrain.getHeight



For Geometry it use class wrapper where it check bounding blockade points and top moveable points(to give possibility to walk on it) by RayCasting



so it can have moveable points on multilevels



i would like to improve it, so if you have some ideas, it would be helpful :slight_smile:

@oxplay2 said:
yes i use mapping by matrix(it is mapped by precision and using int values), but to save memory usage i dont hold neutral points in memory.

And yes, you have right, i will prepare a video, give me some time

The solution is impressive and can be an alternative for NavMesh, as for the specific Level which NavMesh can pretty go wrong in some cases.
For myself it work great, becouse for NPC server it use blindMove solution to make pathfinding faster(becouse it need to be fast for 1000 or more of npc’s).

So i think it is perfect for strategy games, or rpg like UFO series
But it is bad solution for FPS games(becouse here usually we dont need to use multifloor pathfinding)


really ? and why ...

The jme navigation mesh works on multiple levels. It is this library: critterai

@atomix:

i am still a student :wink: dont take me too serious

and i was creating it having on mind MMO games. where usually in open spaces entity dont need to calculate shortest way, so i created blindMove procedure first. At all i should create it in c++, but i didn’t.



everyone can create his own solution or choose ready ones, this is how it work :wink: every idea is good for diffrent types of games.



as @Sploreg said there are pathfinding for multilevel

i didnt known there are multiple levels solution already, but i will continue learning about pathfinding and upgrading Easyfinding.



Its like a hobby :slight_smile:

1 Like

Keep working with yours, it is a good process to see how these things work and you will learn a lot from them in the process.

Any what was that c++ mention I saw above? :wink: You know it won’t make it faster, right?

@Sploreg said:
Keep working with yours, it is a good process to see how these things work and you will learn a lot from them in the process.
Any what was that c++ mention I saw above? ;) You know it won't make it faster, right?


nope, i thinked wrappers for c libs work faster than just a java code :roll: i never tried to write this kind of wrappers, so maybe its reason of my thinking. I have still many to learn

They won’t be faster, don’t waste your time with it. Unless you are a level 65 C programmer :slight_smile: Even then I doubt you will get many gains in performance. All the slowdown in pathfinding is in the algorithm and the number of math calculations (not having to check as many nodes, doing fewer divisions etc.)

yep i know, even array i have [] than [][][](where it give pointer to pointer).



Profiler gived me many help in understanding what is most slowdown :slight_smile: