A* Nodes
As you can probably guess from the name, A* Nodes is a path-finding plugin which uses nodes instead of the normal grid.
Also, the plugin is capable of both synchronous and asynchronous path-finding. (synchronous version doesn't return from the function until it is done, asynchronous sets it going in a separate thread, and will return immediately)
Done:
2d Path-finding (used for 2d and 3d top-down path-finding)
manual addition of nodes
automatic addition of nodes by adding shapes
radius
asynchronous and synchronous path-finding (there's no pause when trying to calculate a very long path)
Up to 31 asynchronous and 1 synchronous searches running at the same time!
Fixed problem with over-guessing remaining distance (meant it didn't find the shortest path!)
built in circle casting
remove dependencies on other plugins
Will do:
3d equivalent (nodes have a Z location)
find slow code and OPTIMIZE!
add some debug drawing commands (eg. draw node positions and shapes)
Example:
rem Asynchronous path-finding example
wait mouse
sync on
asCreateWorld2d 1,0 `get ptr to function(1)
make object sphere 1,2
position object 1,-5,0,-5
make object cube 2,2
position object 2,rnd(100),0,rnd(100)
DefineCube(2)
for i = 3 to 300
clone object i,2
position object i,rnd(100),0,rnd(100)
DefineCube(i)
next i
asCalculateWorldNodes 1,1
start = timer()
index = asBeginFindPath2d(1,1,-5,-5,105,105)
position camera 0,8,0
xro# = 90
yro# = 0
ended = 0
camfollow = 0
dist# = 0.0
node = 0
dist2# = 5.0
node2 = 0
do
if ended
`Comment out the next 3 lines if you don't have the d3d plugin!!!
for i = 1 to num-1
d3d_line3d asGetResultX(1,1,i-1),0,asGetResultY(1,1,i-1),asGetResultX(1,1,i),0,asGetResultY(1,1,i),rgb(255,0,0),1
next i
else
if asEndFindPath2d(1,index) then ended = timer() : num = asGetResultCount(1,1) : camfollow = 1
endif
if camfollow
ndist# = 0.0
n = 0
x1# = asGetResultX(1,1,node)
y1# = asGetResultY(1,1,node)
x2# = asGetResultX(1,1,node+1)
y2# = asGetResultY(1,1,node+1)
d# = sqrt((x2#-x1#)*(x2#-x1#)+(y2#-y1#)*(y2#-y1#))
frac# = dist#/d#
nx# = x1#+(x2#-x1#)*frac#
ny# = y1#+(y2#-y1#)*frac#
position camera nx#,0,ny#
inc dist#,0.05
if dist# >= d# then inc node : dist# = 0.0
x1# = asGetResultX(1,1,node2)
y1# = asGetResultY(1,1,node2)
x2# = asGetResultX(1,1,node2+1)
y2# = asGetResultY(1,1,node2+1)
d# = sqrt((x2#-x1#)*(x2#-x1#)+(y2#-y1#)*(y2#-y1#))
frac# = dist2#/d#
nx# = x1#+(x2#-x1#)*frac#
ny# = y1#+(y2#-y1#)*frac#
point camera nx#,0,ny#
inc dist2#,0.05
if dist2# >= d# then inc node2 : dist2# = 0.0
if node = num-1 then camfollow = 0
if node2 = num-1 then node2 = num-2 : dist2# = d#
else
inc yro#,mousemovex()*0.5
inc xro#,mousemovey()*0.5
rotate camera xro#,yro#,0
move camera (upkey()-downkey())*0.1
move camera right (rightkey()-leftkey())*0.1
endif
sync
loop
end
function DefineCube(objnum)
x# = object position x(objnum)
z# = object position z(objnum)
asAddWorldShape 1,x#-1,z#-1,x#+1,z#-1,x#+1,z#+1,x#-1,z#+1
endfunction
-- UPDATED 07 SEPTEMBER --
Plugin download: HERE
Command list:
asCreateWorld2d - worldid as Integer, valid_path_callback as Integer
asDeleteWorld2d - worldid as Integer
asAddNode2d - Return ? as Integer = (worldid as Integer, x as Float, y as Float)
asRemoveNode2d - worldid as Integer, nodeid as Integer
asFindPath2d - worldid as Integer, result as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float
asBeginFindPath2d - Return ? as Integer = (worldid as Integer, result as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float)
asEndFindPath2d - Return ? as Boolean = (worldid as Integer, searchid as Integer)
asGetResultCount - Return ? as Integer = (worldid as Integer, result as Integer)
asGetResultX - Return ? as Float = (worldid as Integer, result as Integer, index as Integer)
asGetResultY - Return ? as Float = (worldid as Integer, result as Integer, index as Integer)
asCalculateWorldNodes - worldid as Integer, radius as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float, x5 as Float, y5 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float, x5 as Float, y5 as Float, x6 as Float, y6 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float, x5 as Float, y5 as Float, x6 as Float, y6 as Float, x7 as Float, y7 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float, x5 as Float, y5 as Float, x6 as Float, y6 as Float, x7 as Float, y7 as Float, x8 as Float, y8 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float, x5 as Float, y5 as Float, x6 as Float, y6 as Float, x7 as Float, y7 as Float, x8 as Float, y8 as Float, x9 as Float, y9 as Float
asAddWorldShape - worldid as Integer, x1 as Float, y1 as Float, x2 as Float, y2 as Float, x3 as Float, y3 as Float, x4 as Float, y4 as Float, x5 as Float, y5 as Float, x6 as Float, y6 as Float, x7 as Float, y7 as Float, x8 as Float, y8 as Float, x9 as Float, y9 as Float, x10 as Float, y10 as Float
To install:
- Place the .dll in your compilerplugins-user folder
- Place the .ini in your editorkeywords folder
Instructions:
1) create a world using asCreateWorld2d <id>,0
2) add shapes to the world using asAddWorldShape <worldid>,clockwise vertex list...
3) calculate the nodes using asCalculateWorldNodes <worldid>,<radius>
4) use asFindPath2d to find a path from one point to another
(see example for how to do it asynchronously)
Enjoy
____________________________________
How it works
The plugin is split into two parts:
1) The automatic node maker
The automatic node maker takes a series of polygons (stored as a list of clockwise ordered points) and outputs the nodes necessary to get around the shapes.
- Nodes must be at least <radius> distance from every shape
- Nodes only need to be present on outward pointing vertices.
- Nodes cannot be inside a shape
To accomplish this, the plugin moves the border of every shape out by <radius> units, and then again for another 1/100th of the radius.
All the vertices in the second set of polygons generated are checked to see if they are inside any of the polygons generated by the first enlargement.
If they are not in any of them, and they 'stick out' (the angle < 180 degrees) they are added to a single final polygon, which just holds the list of nodes.
All these nodes are added to the world.
Every node in the world is checked with every other node in the world, to see if the can see each other, using either a user function, or a built in one.
In the built in one, the enlarged shape list is used for the ray casting to effectively do a circle cast instead of a ray cast.
If two nodes can see each other a path is created between them.
Algorithms used:
- 2d cross product to move a line outwards
(just change the y to 0-the old x, and x to the old y, then divide by the length to normalise it)
- Line intersection
for each line x1,y1,x2,y2:
A = y2-y1
B = x1-x2
C = A*x1+B*y1
A1/B1/C1 is the A/B/C for line 1
A2/B2/C2 is the A/B/C for line 2
x/y is the final intersection point
det = A1*B2 - A2*B1
if det = 0
-> Lines are parallel
else
-> x = (B2*C1 - B1*C2)/det
-> y = (A1*C2 - A2*C1)/det
2) The path-finder
The path-finder uses the A* path-finding algorithm, which works like so:
Each node has an F,G,H and P value.
G is the total distance to get to the node.
H is the estimated distance to the finish
F is G+H
P points to the node which comes before this node in the path (to follow it back after)
There are two lists of nodes, an 'open' list and a 'closed' list. First of all, the starting node is added to the open list.
Then the loop begins:
1. The node in the open list with the smallest F value is selected.
2. If there are no more nodes in the open list, there is no path from start to finish
3. This node is moved to the closed list.
4. If this node is the finish node, the path is found, exit the loop and just go back up the path by following the P values
5. All the nodes connected to this node are looped through
6. If the node is in the closed list, ignore it
7. If the node is in the open list, and the G value of the selected node plus the distance to the node is less that its current G value
8. Then change the G to the new G value, and change P to point to the selected node
9. Otherwise, ignore it
10. If it's in neither list, add it to the open list
11. The G value is the G value of the selected node, plus the distance from the selected node to this new node
12. The H value is the distance in a straight line from the node to the finish
13. Set P to point back to the selected node
14. Loop back to 1
An explanation for the grid method (which is the same but using cells instead of nodes) can be found here:
http://www.policyalmanac.org/games/aStarTutorial.htm
I hope some people learn from this!
