 |
|
AMX Mod X Plugin Approver
Join Date: Sep 2013
Location: Romania
|

05-18-2021
, 05:20
Re: NPC Waypoint system
|
#2
|
Firstly, don't even bother trying to implement A* in a plugin. To get a good temporal complexity you need data structures(like priority queues) which pawn/amxx core do not provide. You can try to implement them by hand, but they will likely suck if you don't know what you are doing.
Secondly, just by running A* every time you need an npc to recompute the path you will manage to freeze the server for a while if you have a bigger/more complicated map or more than a few npcs.
zbots work in the following way:
-step over the entire playable area and build a graph where an edge means an entity can travel along that edge from a node to another
-using the waypoint graph generated earlier, try to create a navigation mesh by merging as many nodes as possible into one big area. The key here is that inside an area there should be no obstacles. The entity should be able to move in a straight line while inside an area. You should only need to pathfind between different areas
-find the areas in which your start and destination points are, and if in different areas, run a pathfinding algorithm like A* between them. If in the same area, just move in a straight line.
Then you also have to write a pretty complicated movement code so your npcs can actually follow the path. Also note that the path will not be ideal and the movement logic should be able to compensate for it.
In short, it is difficult, especially if you never worked with graphs, A*, heuristic functions or data structures before.
__________________
Last edited by HamletEagle; 05-18-2021 at 05:22.
|
|
|
|