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]