PathFinder status

[LogicParrot]

Last update: Friday, 25 December, 2015

Related thread: Mob status

This thread is an overview of the current status of the PathFinder and what I plan to improve. For specific development issues, see the PathFinder Github label. Note that this reflects the status of the Master branch.


PathFinder to-do list:

• Done: Implement 3d A* that can calculate the shortest path between 2 points. For mob integration, see the Mob Status thread.
  
• Done: Add flexible bounding boxes.
  
• Done: Pick closest path when no destination to target.
  
• Partially Done: Fence handling. Mobs will not pass fences, but they behave strangely if the player is standing near a fence.
  
• Done: Deal with falls.
  
• Done: Water handling.
  
• Gates, doors and trapdoors handling. Currently, they are always considered closed.
  
• Ladder Handling. currently, ladders are ignored.
  
• Spider climbing.
  
• Underwater PathFinding for squids and guardians.
  
• Line-of-sight optimization. Mobs should ditch the pathfinder and walk in straight line when possible to avoid weird grid snapping.
  

PathFinder might-do list:

• Custom solids. e.g. some mobs may want to avoid cobweb and some ghost might want to walk through dirt.
  
• Flight.
  
• Dijkstra.
  

Bugs:

• When a cell's G value is updated, the priority queue will have a stale value and therefore a cell with a non-minimal G might be selected. Check if this has any practical significance.
  

Optimizations to-do list:

• Done: Get rid of DoWithChunk.
  
• Done: Vector3i wherever Vector3d will never be needed.
  
• Can I get rid of sqrt?
  
• Idle mobs optimization.
  

Some optimizations that *might* be implemented later

• Jump point search
  
• Use a "Reversed Dijkstra" to make things very efficient. This would basically create a "path force field" around each player, any mob in that field can travel to the player without any additional computation. So, the cost of calculating paths would become k*Players and not k*Mobs.
  

Old post:
[spoiler]
Related Github Issue: https://github.com/mc-server/MCServer/issues/1391

I can implement a function for A* pathfinding, which could be used for the AI.
My knowledge of the codebase is next to nill. So I have some questions:

Is any path-finding implemented?
Is such a function desired?
What are the general plans for AI?


***My general plan***

Despite my lack of knowledge in the code base, I can implement a "game-agnostic" function which can find the path, here is rough declaration of such a function:

point * point_array find_path(x_from,y_from,z_from,x_to,y_to,z_to,max_jump,character_width,character_length,character_height)

max_jump determines the character's ability to traverse vertically.
0 means the character will never change its Z position, e.g. a silverfish.
1 is typical for most mobs.
A spider can scale walls, therefore this can have a larger value, such as 50.

The way the path is returned can vary, my initial thought was an array of points.

character_width,character_length,character_height determine how big the character is. e.g. a zombie shouldn't path-find through a door with a height of 1.

The only code base knowledge I need in order for me to implement it is a function which returns whether or not a block is occupied, something like
bool is_solid(int x,int y,int z)

For debugging purposes, I'd also need to place some marker blocks, e.g. place_block(int x,int y,int z, blocktype)

After this thing works, I can convert it to a non-blocking function. (A function which is partially executed each tick to prevent a game freeze).

Trivial: Deciding whether x_from,y_from,z_from define the center point of a character or one of its edges.

Less trivial: Determining what happens if a calculated path is no longer valid. What does Vanilla do in such a case? The easy solution is just going along the path until encountering an obstacle, and then recalculating.

If there are minecraft creatures which can go down ledges but can't go up, max_jump can be split into max_up and max_down.

Tell me your thoughts of this!

Github issue: https://github.com/mc-server/MCServer/issues/1391

P.s. my github identity is " Wiseoldman95"
Feel free to confirm this by checking the "URL" in wiseoldman95's profile
https://github.com/wiseoldman95


Files that may be related to pathfinding:
https://github.com/mc-server/MCServer/bl...ingBox.cpp
[/spoiler]

[xoft]

Hi,
I believe there is some basic form of pathfinding already implemented in the codebase, although I can't point you exactly to the code. I think @tigerw could shed some light here.
As for your questions, first let me note that a jump is a different thing than a spider's wallclimb, and we will need pathfinding for flying mobs, too, so you might want to include that in your analysis.
Also note that blocks in MC aren't just solid / non-solid, there are doors, trapdoors, fences, fencegates, halfslabs, stairs, soulsand, water and other special cases that will need some thinking about. It might be better to get a function that gives you the block's "non-passable bounding box" based on the block's placement. You will need to take into account the non-integral coordinates used.

As for mobs, each entity has its size already defined in cEntity::GetWidth() and cEntity::GetHeight(); the entities use an axis-aligned bounding box with the same dimension in X and Z. The entity position is anchored in the center of the entity's bounding box's bottom side (MidX, LowY, MidZ).

The pathfinding will most likely want to run inside the chunkmap's lock, so that it can directly access the chunk data. You will have to do so using the cWorld::DoWithChunk() method to get you in, and using the callback parameter for the actual calculation. The cBlockLineTracer class should provide an example of doing this. You can then use cChunk::GetBlock() and cChunk::SetBlock() to query and set blocks.

[LogicParrot]

As for your questions, first let me note that a jump is a different thing than a spider's wallclimb/

From a path-finding perspective, they are the same. Perhaps the variable name I picked was terrible.

and we will need pathfinding for flying mobs, too, so you might want to include that in your analysis.

I did not take that into account. However, the Vanilla ghasts are rather dumb, we probably need primitive path-finding for that.

Assuming we do need A* for flying creatures, it would be actually easier than walking creatures. 3d a* actually works with complete disregard to ground-level, and implementing walking creatures is actually slightly harder because one must restrict the possible paths.

Also note that blocks in MC aren't just solid / non-solid, there are doors, trapdoors, fences, fencegates, halfslabs, stairs, soulsand, water and other special cases that will need some thinking about.

Yet they can all be summed up to "traversable" and "non-traversable", correct?

As for mobs, each entity has its size already defined in cEntity::GetWidth() and cEntity::GetHeight(); the entities use an axis-aligned bounding box with the same dimension in X and Z. The entity position is anchored in the center of the entity's bounding box's bottom side (MidX, LowY, MidZ).

Great

It might be better to get a function that gives you the block's "non-passable bounding box" based on the block's placement. You will need to take into account the non-integral coordinates used.

Why is that needed?

[xoft]

Ghasts in vanilla do not actively pursue the player, so they don't need real pathfinding. Blazes do not pursue the player either, they just fly up / down. Bats fly around randomly, also don't need a pathfinding for that. I guess we can do without the flying mobs for now.

Consider a door for a moment. Is it a passable block or not? It depends on the surroundings; you cannot even do with a "closed" / "open" states because the door can be closed and yet be passable because it is lined up to a wall differently. Also it only leaves a ~0.8m wide corridor, so it is passable only for mobs narrower than 0.8m.

As another example, the ladder block cuts away a 1/16th of the block, so an entity that is 1 block wide can't pass in 1-block-wide corridor lined with ladders on the sides. Similarly with carpets and entity height, and halfslabs, more noticeably.

[LogicParrot]

Ghasts in vanilla do not actively pursue the player, so they don't need real pathfinding. Blazes do not pursue the player either, they just fly up / down. Bats fly around randomly, also don't need a pathfinding for that. I guess we can do without the flying mobs for now.

I will implement flight anyways, it's just a couple of lines less than the ground thing.

Consider a door for a moment. Is it a passable block or not? It depends on the surroundings; you cannot even do with a "closed" / "open" states because the door can be closed and yet be passable because it is lined up to a wall differently. Also it only leaves a ~0.8m wide corridor, so it is passable only for mobs narrower than 0.8m.
As another example, the ladder block cuts away a 1/16th of the block, so an entity that is 1 block wide can't pass in 1-block-wide corridor lined with ladders on the sides. Similarly with carpets and entity height, and halfslabs, more noticeably.

Fair enough. I will just replace is_solid with is_traversable(x,y,z,mob_width,mod_height,mob_length), which is a function which returns false if the mob can't possibly be standing at that particular spot. (Due to a solid block, a bounding box, etc).
Edit: This seems to be a bit more involved than that

[LogicParrot]

Analysis - Bounding boxes

EDIT: Okay, this has some missing bits. Words have failed me, I will post some pseudo-code instead later on.

Bounding boxes are tricky, here is my proposed solution. peer review will be appreciated.

For simplicity, let us assume we have a 2d world.

Intro: The simplest version of A* divides the world into blocks, each X,Y is either solid or empty, let us define a function get_solid(int x,int y), which simply returns true if the position is occupied by a block.

The problem: Minecraft: might have more exotic structures, such as half-blocks.

One solution is to use a more complex algorithm. My proposed solution is hopefully better.

1. Stick to regular A*, change nothing except the get_solid(int x,int y) function.
2. Instead of a simple get_solid(int x,int y), our new function which will be called get_traversable(int x,int y), checks if the player can possibly stand right in the center of the block (x+0.5,y+0.5), (it checks the bounding box of the character as if it were standing on (x+0.5,y+0.5) and scans for collisions with surrounding bounding boxes.)
If there are no collisions, false is returned and A* continues as if there is no block.
If there are collisions, we swap (x+0.5,y+0.5) with (x+m,y+n) where m is the average point between the position of the rightmost and leftmost bounding boxes of the surrounding objects, and n is the average point between the uppermost and bottommost bounding boxes of the surrounding objects. We check for collisions again, if none found, false is returned and A* continues as if there is no block.
If a collision is found, true is returned and A* continues as if there is a solid block.

[sphinxc0re]

Also we should give mobs a range in which they can profit from their pathfinding abilities. The range should also be changeable by commands or the API

[xoft]

I don't think a query of "can be here" will cut it. You need something more advanced, and luckily, there is something that might work: Get a function CanMove, that gets the start and end pos, which must be exactly 1 block apart, and the entity dimensions, and return the bool result and the Y coord of the dest point.. That way you can make your A* algorithm without many changes and it will work even for doors and such. It still won't work for things like traversing a hole over a row of opened trapdoor's ledges, but hey, we'll even be better than vanilla because our zombies will walk around doors instead of trying to knock them down

[LogicParrot]

I don't think a query of "can be here" will cut it. You need something more advanced, and luckily, there is something that might work: Get a function CanMove, that gets the start and end pos, which must be exactly 1 block apart, and the entity dimensions, and return the bool result and the Y coord of the dest point.. That way you can make your A* algorithm without many changes and it will work even for doors and such. It still won't work for things like traversing a hole over a row of opened trapdoor's ledges, but hey, we'll even be better than vanilla because our zombies will walk around doors instead of trying to knock them down

A canmove function sounds a lot more costly than my proposed get_traversable, and since the path-finding function will be called so many times, performance is very important. Do you think a canmove offers any advantage in comparison to get_traversable?

Nevertheless, it might make my job easier

Btw, I intend to make the "is it legal over there" function fully separate from the A* algorithm, making it easily swappable later on. In fact, I plan to begin with a dumb "Is there a solid block with complete disregard to the bounding boxes?" and improve it later on.

---

Also we should give mobs a range in which they can profit from their pathfinding abilities. The range should also be changeable by commands or the API

Of course. But that would be on the mob-level and not the pathfinding level. e.g. A zombie's code:
If (Player_is_nearer_than_50_blocks) do_pathfinding(......);

[LogicParrot]

Do I have to deal with rotating bounding boxes?