Legacy GM mp_path and AI movement query

B

Bogan666

Guest
I'm using mp_path functions for my AI currently, and from what I have setup it works well. The only issue I'm *currently* running into is how I've currently got it setup and how it works.
I've got something like this set up:
nearest_tree = instance_nearest(x,y,obj_tree);
mp_grid_path(grid, path,x,y, nearesttree.x+16,nearesttree.y+16,false);

This works great! Minis one issue, if a tree is the closest tree or more than one npc they'll both go to it and stack on eachother, I can't think of a way for a tree to be marked as occupied and have it not come up as the nearest tree unless there is no one on it.

Any help would be appreciated
 

NightFrost

Member
You have to create a routine that gets all trees, sorts them by distance, and goes through them starting from nearest until it finds a tree that is not marked as occupied. When an NPC is told to cut a tree, it gets the nearest tree by calling that function. When the NPC approaches a tree, it constantly monitors the state of that tree, and if it becomes occupied, it calls the routine to find another tree. When an NPC gets to a tree, it marks it as occupied.

You'll also notice that nearest, as bird flies, is not necessarily the nearest to pathfind. There might be a tree two grid cells away, but path has to go around 20-cell wall, but it is still deemed closer than another that is three grid cells away but with unobstructed path. Many systems deem this an acceptable price, since it would be too expensive to get path lengths to every potential target. Or they get into more complex pathfinding systems, but that's one deep rabbit hole to jump into.
 
B

Bogan666

Guest
You have to create a routine that gets all trees, sorts them by distance, and goes through them starting from nearest until it finds a tree that is not marked as occupied. When an NPC is told to cut a tree, it gets the nearest tree by calling that function. When the NPC approaches a tree, it constantly monitors the state of that tree, and if it becomes occupied, it calls the routine to find another tree. When an NPC gets to a tree, it marks it as occupied.

You'll also notice that nearest, as bird flies, is not necessarily the nearest to pathfind. There might be a tree two grid cells away, but path has to go around 20-cell wall, but it is still deemed closer than another that is three grid cells away but with unobstructed path. Many systems deem this an acceptable price, since it would be too expensive to get path lengths to every potential target. Or they get into more complex pathfinding systems, but that's one deep rabbit hole to jump into.
Right, makes sense.
What I'm having a tough time grasping is letting the npc know that a tree is occupied. I have code currently on the tree that if there is an npc on it mark it as an "active_tree", but have no idea how to do about it.
I could probably think of how to go about creating a routine to get all trees/find the nearest, or find info about how to do that. But how would I go about using the info of "this is the nearest tree that is currently in use" I don't know what lines of code Id need to check that variable inside of the tree.
Thanks for the reply though, thought no one was going to.
 

NightFrost

Member
You can use ds priority queue for the finder routine. Loop through all trees, and for each calculate distance to calling NPC, then add to queue with tree ID as value, distance as priority. Next, while-loop the queue until its size is zero. Get and delete from queue the tree with shortest distance (var _This_Tree = ds_priority_delete_min()), check if it has occupied variable set (if(_This_Tree.Occupied == false)) and either make it pathing target and break out of the loop, or continue. If you emptied the queue without finding a target, it means there are no valid targets.
 
B

Bogan666

Guest
You can use ds priority queue for the finder routine. Loop through all trees, and for each calculate distance to calling NPC, then add to queue with tree ID as value, distance as priority. Next, while-loop the queue until its size is zero. Get and delete from queue the tree with shortest distance (var _This_Tree = ds_priority_delete_min()), check if it has occupied variable set (if(_This_Tree.Occupied == false)) and either make it pathing target and break out of the loop, or continue. If you emptied the queue without finding a target, it means there are no valid targets.
ds_proirity_queue seems to be a GMS2 feature.. I'm on 1.4
 

Yal

šŸ§ *penguin noises*
GMC Elder
Priority queues are in GMS1 as well, but they might be named just ds_priority there.
 
Top