Research on a new method of pathfinding algorithm for performance improvement
Recently, after adding wolves, I set the wolves' field of view to be wider than that of rabbits and conducted tests, during which I confirmed that the A* algorithm was not performing well.
This is because, in the current Breathing World, it uses coordinates that are subdivided into a width and height 16 times larger than the 1920 x 1080 terrain and plant coordinates.
So, the wolf server is actually currently stopped.
The wolves visible on the screen right now can just be considered cached data.
The existing A* algorithm is very well-known and has already been proven to deliver sufficiently good performance.
However, despite my limited skills and knowledge, I am challenging myself in this project to implement a pathfinding algorithm that performs far better than this.
The basic approach is as follows:
- Determine the straight path from the starting point to the destination. (Utilizing Bresenham's Line Algorithm)
- While calculating the path, if an obstacle is encountered, immediately stop and recognize the obstacle.
- Retrieve the outline information of the obstacle.
- Among the outline information, select the optimal point for bypassing the obstacle. (This part is the core)
- Combine the starting point and the bypass point to create a kind of waypoint coordinate.
- Subsequently, repeat the same process from the bypass point to the destination.
- Ultimately, the path is constructed like this: (starting point, waypoint1, waypoint2, ..., waypointN, destination).
This is fundamentally the same concept as the ray concept used in 3D engines.
However, since I am working in a 2D context and diagonal movement is not allowed, I only made slight adjustments.
I would appreciate it if you could wish me success so that I can soon share the good news of my achievement.
Farer
