Making a pathfinder by mapping bricks

Blockland Forums > Modification Help

<< < (3/4) > >>

Destiny/Zack0Wack0:

--- Quote from: Ipquarx on August 11, 2011, 04:33:49 PM ---sounds like its possible. but, there seems to be 1 problem with destiny's solution, that is that it goes in the first direction that is open. givin the right (or wrong) combination of directions, it may just loop forever. and also, it seems like that isnt pathfinding, its trying every possible direction until you finally get it righ, basically a brute-force attack.

--- End quote ---
I was referring to AI movement in general. Obviously you'd make it learn. If you want waypoint pathfinding look at this: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

M:
When I made pathfinding it was based on a manually built nodegraph. It implemented something much like the algorithm Zack0Wack0 linked there, except mine went through the whole nodegrid keeping a list of the nodes it had been through for each iteration (to try to prevent infinite loops, they still occurred though) and the total distance.

The function calls itself at the new node with the current path recursively, though it had a whole bunch of schedule-and-callback shenanigans so the bot would enter a "thinking" state where it would begin pathfinding, and upon completion make a callback which pushes the path onto the bot and starts its movement.

So, borrowing the first frame of the Djikstra's algorithm runtime image from Wikipedia there:

Bot is at node 1, connected to 2, 3, and 6
Call function on nodes 2, 3 and 6:
findPath(bot,2,"1",7)
*not ideal path, not documenting*
findPath(bot,3,"1",9)
Node 3, visited 1, distance 9
Check connected nodes 1, 4, 6
Visited 1, skip
findPath(bot,4,"1 3",20)
Node 4, visited 1, 3, distance 20
Check connected nodes 2, 3, 5
5 is target node, distance 6 for total 26 - return "26 3 4 5"
findPath(bot,6,"1 3",11)
Node 6, visited 1, 3, distance 11
Check connected nodes 1, 3, 5
5 is target node, distance 9 for total 20 - return "20 3 6 5"
findPath(bot,6,"1",14)
*not ideal path, not documenting*

Return distances of 26 and 20, 20 is lower so take path sent with 20 "3 6 5" - go to node 3
On reach node 3, go to node 6
On reach node 6, go to node 5
On reach node 5, call destination reached callback

Obviously this can get quite long hence all the schedule shenanigans, scheduling 10ms for every node, so a path to the destination with 5 nodes will literally return faster than a longer path as well (and then all the other "thinking" schedules are cancelled)

And also obviously, bots aren't always going to be standing right at a node - bots search for the nearest node to their location that they can raycast to, then begin the pathfinding process from that node while they walk there. You could also use four more raycasts to check a 'bounding' area of the bot from their current location to the node and see if it's really clear to walk, after doing a basic check so you do one raycast per non-feasible node and five total per potentially feasible node.

However, creating a pathfinder that will literally find paths on its own is more or less impossible - well, perfectly possible I guess, if you don't mind it freezing your game for several minutes while it pathfinds.
However you can always just set up a nodegrid for your bot deathmatchers or whatever.

Xalos:
It's perfectly possible to create a bot that can pathfind, but there are several important problems:

1. looping through the ServerConnection on a server with any number of builds will lag you for at least a second.

2. it won't find any players. Yes, there are aimbots that can; no, I'm not giving you one here.

3. raycasts don't work on the client's side.

Nexus:

--- Quote from: Xalos on August 16, 2011, 09:27:16 AM ---It's perfectly possible to create a bot that can pathfind, but there are several important problems:

1. looping through the ServerConnection on a server with any number of builds will lag you for at least a second.

2. it won't find any players. Yes, there are aimbots that can; no, I'm not giving you one here.

3. raycasts don't work on the client's side.

--- End quote ---

This is all correct, but I'm not completely sure that we are restricting ourselves to client side code.

Ipquarx:

--- Quote from: Nexus on August 16, 2011, 11:21:01 AM ---This is all correct, but I'm not completely sure that we are restricting ourselves to client side code.

--- End quote ---
Exactly right. Doesnt matter if its client-sided or not, whichever is simpler.
Im just going to scrap this anyway, would take too long to make, givin I could figure out how it would work.

Navigation

 Message Index

Go to full version