Raised This Month: $ Target: $400
 0% 

NPC Waypoint system


  
 
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
HamletEagle
AMX Mod X Plugin Approver
Join Date: Sep 2013
Location: Romania
Old 05-18-2021 , 05:20   Re: NPC Waypoint system
Reply With Quote #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.
HamletEagle is offline
 



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 20:00.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode