incoming giant block of text
keep in mind i am no programmer, i've never tried anything like this before.
i realise most of this is redundant and inefficient. it doesn't handle other units at all.
basically the entire thing is temporary, i just wanted to get it working and make sure i got it down before i broke it down into sub functions and made it actually efficient.
it used to avoid structures although somehow i broke that so i removed it for now
Pathfinding
Options: Action
Return Type: (None)
Parameters
Unit = No Unit <Unit>
Order = No Order <Order>
Grammar Text: Pathfinding(Unit, Order)
Hint Text: (None)
Custom Script Code
Local Variables
Nodes = No Point <Point[9][100]>
Node Open? = false <Boolean[9][100]>
Node Closed? = false <Boolean[9][100]>
Picked Node = 0 <Integer>
Path Found = false <Boolean>
HV Score = 10 <Integer>
D Score = 14 <Integer>
G = 0 <Integer[9]>
H = 0 <Integer>
F = 0 <Integer>
Lowest F = 100000 <Integer>
n = 0 <Integer>
Tentative is Better = true <Boolean>
Nodes to Destination = 0 <Integer>
Calculate = 0 <Integer>
Calculate 2 = 0 <Integer>
Path = No Point <Point[100]>
Actions
General - While (Conditions) are true, do (Actions)
Conditions
Path Found == false
(Unit is alive) == true
Actions
Variable - Set Nodes[0][0] = (Position of Unit)
Variable - Set Nodes[1][0] = ((Position of Unit) offset by (0.0, 1.0))
Variable - Set Nodes[2][0] = ((Position of Unit) offset by (1.0, 1.0))
Variable - Set Nodes[3][0] = ((Position of Unit) offset by (1.0, 0.0))
Variable - Set Nodes[4][0] = ((Position of Unit) offset by (1.0, -1.0))
Variable - Set Nodes[5][0] = ((Position of Unit) offset by (0.0, -1.0))
Variable - Set Nodes[6][0] = ((Position of Unit) offset by (-1.0, -1.0))
Variable - Set Nodes[7][0] = ((Position of Unit) offset by (-1.0, 0.0))
Variable - Set Nodes[8][0] = ((Position of Unit) offset by (-1.0, 1.0))
Variable - Set n = 0
General - While (Conditions) are true, do (Actions)
Conditions
Path Found == false
(Unit is alive) == true
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
n > 0
Then
Variable - Set Nodes[0][n] = Nodes[Picked Node][(n - 1)]
Variable - Set Nodes[1][n] = (Nodes[Picked Node][(n - 1)] offset by (0.0, 1.0))
Variable - Set Nodes[2][n] = (Nodes[Picked Node][(n - 1)] offset by (1.0, 1.0))
Variable - Set Nodes[3][n] = (Nodes[Picked Node][(n - 1)] offset by (1.0, 0.0))
Variable - Set Nodes[4][n] = (Nodes[Picked Node][(n - 1)] offset by (1.0, -1.0))
Variable - Set Nodes[5][n] = (Nodes[Picked Node][(n - 1)] offset by (0.0, -1.0))
Variable - Set Nodes[6][n] = (Nodes[Picked Node][(n - 1)] offset by (-1.0, -1.0))
Variable - Set Nodes[7][n] = (Nodes[Picked Node][(n - 1)] offset by (-1.0, 0.0))
Variable - Set Nodes[8][n] = (Nodes[Picked Node][(n - 1)] offset by (-1.0, 1.0))
Else
Variable - Set G[1] = HV Score
Variable - Set G[2] = D Score
Variable - Set G[3] = HV Score
Variable - Set G[4] = D Score
Variable - Set G[5] = HV Score
Variable - Set G[6] = D Score
Variable - Set G[7] = HV Score
Variable - Set G[8] = D Score
Variable - Set Lowest F = 100000
Variable - Set Node Open?[0][n] = false
Variable - Set Node Closed?[0][n] = true
General - Pick each integer from 1 to 8, and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
Node Closed?[(Picked integer)][n] == false
Then
Variable - Set H = ((Integer(((Abs(((X of Nodes[(Picked integer)][n]) - (X of (Target position for Order))))) + (Abs(((Y of Nodes[(Picked integer)][n]) - (Y of (Target position for Order)))))))) * 10)
Debug - Display (Text(H)) as debug output using Type 1, and Do display it in the game window
Variable - Set F = (G[(Picked integer)] + H)
Debug - Display (Text(F)) as debug output using Type 1, and Do display it in the game window
Variable - Set Node Open?[(Picked integer)][n] = true
Variable - Set Tentative is Better = true
Debug - Display (Combine ((Text((Picked integer))), " - ", (Text(F)))) as debug output using Type 1, and Do display it in the game window
General - If (Conditions) then do (Actions) else do (Actions)
If
F < Lowest F
Then
Variable - Set Tentative is Better = true
Variable - Set Lowest F = F
Else
Variable - Set Tentative is Better = false
General - If (Conditions) then do (Actions) else do (Actions)
If
Tentative is Better == true
Then
Variable - Set Picked Node = (Picked integer)
Variable - Set Path[n] = Nodes[Picked Node][n]
Else
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[Picked Node][n] is in (Region((Target position for Order), 1.0))) == true
Then
Variable - Set Path Found = true
Debug - Display "Found !" as debug output using Type 1, and Do display it in the game window
Else
Else
Variable - Modify Nodes to Destination: + 1
Variable - Modify n: + 1
Unit - Order (Triggering unit) to ( Move targeting Path[1]) (Replace Existing Orders)
General - Pick each integer from 2 to (Nodes to Destination - 1), and do (Actions)
Actions
Unit - Order (Triggering unit) to ( Move targeting Path[(Picked integer)]) (After Existing Orders)
things im aware of are
pretty sure im not tracking G correctly.
creating nodes dynamically as they are required. i dont think this is the best way. it also causes a problem where im having overlapping nodes.
i tried making a huge grid of nodes at game init and using those. but i hit the 8192 array limit and although i was able to create a way to find the closest node to triggering unit. i had great difficulty, finding the 8 surrounding nodes and working out which was which.
anyway theres my horrible implementation. i looked at alot of source code that had this crunched down to small blocks but i dont retain enough programming knowledge to properly translate it.
*EDIT*
just realised i have 2x while loops with indentical conditions. weird. wonder how that happened.
i've gotta goto sleep now. it's really late. or should i say early? 7:30am :<
thanks again for any help you can provide <3
I have no idea what you're doing, but if you can figure this out, I can really use something like it in a map I'm working on now.
Right now I just have a bunch of points telling my units where to go so it is really clunky. I want to come up with some kind of algorithm for the unit's movement and for checking pathing.
Also, What is A* and where can I find out more about it?
He wants to use the A* pathing methods to restrict a unit to 8 directions. Units in sc2 can move in a full 360 degree range. Units from sc1 can only move in 8 directions ( compass points N,S,E,W,NE,SE,SW,NW). He wants to recreate that 8-direction restriction.
This isnt entirely accurate, the .grp files themselves store up to 17 frames per side, including North and South, forming up to 32 directions total.
still trying.
redesigned it again, feels alot closer but wont work out a path if any obstruction. pretty sure im still not counting G properly but all the source code and pseudocode i've looked at hasn't really helped me with that.
this time i have the map attached ready to go
i implemented a visual aid and a 0.0625 delay so you can see it calculate the path as it goes. (it will draw nodes and color them red/green/blue based on nodes current status (open/closed/checking))
check that my formula is actually correct (i have my doubts even tho it works in the video)
efficiency (is my trigger a piece of shit that runs way slower than it should?)
reconstructing the path (relates to first point. i dont think im setting parent nodes correctly for this.)
group unit movement
best way to implement it.
theres still so very very much i do not know about this system that i need help with.
gawd, what a learning experience. so
feel like i've got the algorithim done finially.
whats left? well it's super super super slow. reading up on this the best way to speed it up seems to be sorting the nodes or a implementing weighted a*
ideally the sorting method if im not too stupid
screenshot for further update...
code in a few posts above can be ignored. code is almost completely different now.
Maverck you should release the full algorithm once your done making it efficient as a library, because this could prove very useful for other types of maps.
yea. i intend to.
community helps me i'll help them ;) lol
anyway, i've got it down, but it needs some serious optimization.
the screenshot below hits the trigger runtime limit of 300-400ms and ends prematurely, the example i've been working off is http://www.briangrinstead.com/files/astar/
his maxes at about 20ms
i'm pretty sure i know whats causing mine to take so long to run
General - Pick each integer from 1 to (Number of Nodes - 1), and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[(Picked integer)] is in (Region(Picked Node, 1.5))) == true
Closed Nodes[(Picked integer)] == false
so this is a nested loop which picks every node created and checks if it's not closed and is adjacent to the currently selected node
any ideas on how to resolve this?
will probably clean up my trigger abit and comment the hell out of it and post it here later today.
yea. i intend to.
community helps me i'll help them ;) lol
anyway, i've got it down, but it needs some serious optimization.
the screenshot below hits the trigger runtime limit of 300-400ms and ends prematurely, the example i've been working off is http://www.briangrinstead.com/files/astar/
his maxes at about 20ms
i'm pretty sure i know whats causing mine to take so long to run
General - Pick each integer from 1 to (Number of Nodes - 1), and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[(Picked integer)] is in (Region(Picked Node, 1.5))) == true
Closed Nodes[(Picked integer)] == false
so this is a nested loop which picks every node created and checks if it's not closed and is adjacent to the currently selected node
any ideas on how to resolve this?
will probably clean up my trigger abit and comment the hell out of it and post it here later today.
I cant think of a quicker way of doing it atm, but perhaps you can look at the java code of his A* app and see if you can find how he did it. You might be able to implement it in the GE. But IDK if you can read Java. I can't but it might be easier to follow if you know what he's trying to do.
Pathfinding 2 Documented
Options: Action
Return Type: (None)
Parameters
Unit = No Unit <Unit>
Source = No Point <Point>
Destination = No Point <Point>
Grammar Text: Pathfinding 2 Documented(Unit, Source, Destination)
Hint Text: (None)
Custom Script Code
Local Variables
path found = false <Boolean>
Picked Node = No Point <Point>
Picked Node Index = 0 <Integer>
New G = 0 <Integer>
Lowest F Node = No Point <Point>
Lowest F Index = 0 <Integer>
new is better = true <Boolean>
Actions
------- Create Starting Node and set H and F Values
Create Node(Source, 0)
Variable - Set H[1] = (Get Dist(Nodes[1], Destination))
Variable - Set F[1] = (G[1] + H[1])
Variable - Set Open Nodes Sorted[1] = 1
Variable - Modify Number of Open Nodes: + 1
Variable - Set Picked Node = Source
------- Initiate main loop
General - While (Conditions) are true, do (Actions)
Conditions
path found == false
Actions
------- create 8 nodes around selected node
------- will not create a new node if another node is already present
General - Pick each integer from 1 to 8, and do (Actions)
Actions
Create Node(Picked Node, (Picked integer))
------- Binary Heap Sorting - Grabs the variable at the top, removes it from the heap and then resorts
Variable - Set Picked Node = Nodes[Open Nodes Sorted[1]]
Variable - Set Picked Node Index = Open Nodes Sorted[1]
Bubble Down()
------- Closes Selected Node
Variable - Set Open Nodes[Picked Node Index] = false
Variable - Set Closed Nodes[Picked Node Index] = true
------- if selected node is destination (path is found) end the main loop
General - If (Conditions) then do (Actions) else do (Actions)
If
(Picked Node is in (Region(Destination, 1.0))) == true
Then
Variable - Set path found = true
Else
------- creates more nodes around currently selected node (might be redundant, or the first one might be, needs checking)
General - Pick each integer from 1 to 8, and do (Actions)
Actions
Create Node(Picked Node, (Picked integer))
------- cause of severe performance loss
------- picks every node and checks if it's adjacent to selected node and not closed
General - Pick each integer from 1 to (Number of Nodes - 1), and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[(Picked integer)] is in (Region(Picked Node, 1.5))) == true
Closed Nodes[(Picked integer)] == false
Then
------- Set New G
------- this is the G score of the distance to the current node + the G to get from current node to picked node
Variable - Set New G = (G[Picked Node Index] + (Get G(Picked Node, Nodes[(Picked integer)])))
------- Node is not Open or Closed?
------- Open it.
General - If (Conditions) then do (Actions) else do (Actions)
If
Open Nodes[(Picked integer)] == false
Then
Variable - Set Open Nodes[(Picked integer)] = true
Variable - Set new is better = true
Else
------- if this path is better or first time seeing this node
General - If (Conditions) then do (Actions) else do (Actions)
If
Or
Conditions
G[(Picked integer)] == 0
New G < G[(Picked integer)]
Then
Variable - Set new is better = true
Else
Variable - Set new is better = false
------- path is better, recalculate nodes and set new parent (Parent Node is the node that was used to get to picked node)
General - If (Conditions) then do (Actions) else do (Actions)
If
new is better == true
Then
Variable - Set Nodes Parent[(Picked integer)] = Picked Node
Variable - Set Nodes Parent Index[(Picked integer)] = Picked Node Index
------- H = Distance from picked node to destination
Variable - Set H[(Picked integer)] = (Get Dist(Nodes[(Picked integer)], Destination))
------- G = cost so far to get to this node
Variable - Set G[(Picked integer)] = New G
------- weighted F
------- F typically is G + H, but it's weighted so G + (5 * H)
Variable - Set F[(Picked integer)] = (G[(Picked integer)] + (5 * H[(Picked integer)]))
------- first time seeing this node? add it to the heap and sort
General - If (Conditions) then do (Actions) else do (Actions)
If
Node Seen?[(Picked integer)] == false
Then
Variable - Modify Number of Open Nodes: + 1
Variable - Set Open Nodes Sorted[Number of Open Nodes] = (Picked integer)
Variable - Set Node Seen?[(Picked integer)] = true
Bubble Up()
Else
Else
Else
------- construct path using parent nodes
Reconstruct Path(Unit, Source, Picked Node Index)
Reset Vars()
the record idea is something i've thought about but im not sure how i'll get the index of that node...
*EDIT*
ok after thinking about it for a minute i've come up with the following idea.
when a node is selected it will inherit adjacent nodes from it's parent. it will then check these if they are within a distance. ones too far away will be removed and overwritten with new nodes that are created.
the screenshot i last posted would hit the trigger execution time limit
so thats about 400 nodes
now it takes 41ms to run which is perfect.
now i just have to develop the best way to make units use this.
off the top of my head im thinking of adding units to a variable and have a running thread which picks units from this variable one at a time.
the screenshot i last posted would hit the trigger execution time limit
so thats about 400 nodes
now it takes 41ms to run which is perfect.
now i just have to develop the best way to make units use this.
off the top of my head im thinking of adding units to a variable and have a running thread which picks units from this variable one at a time.
ideas?
Try this:
Events
selected units use move ability
Condition
unit is ground unit = true
Actions
Your Custom Action, with values changed to fit the events and conditions.
Or you could just do one big trigger, with an if then else event covering each ground unit. Make the trigger check to see what unit it is, then follow up with the appropriate action once it's found the unit. This way you aren't running any other actions than you necessarily have to. But you could also just do individual triggers for each unit, and that might give similar results.
41ms is still kind of high isn't it, does it work efficiently enough in-game?
incoming giant block of text
keep in mind i am no programmer, i've never tried anything like this before.
i realise most of this is redundant and inefficient. it doesn't handle other units at all.
basically the entire thing is temporary, i just wanted to get it working and make sure i got it down before i broke it down into sub functions and made it actually efficient.
it used to avoid structures although somehow i broke that so i removed it for now
Pathfinding
Options: Action
Return Type: (None)
Parameters
Unit = No Unit <Unit>
Order = No Order <Order>
Grammar Text: Pathfinding(Unit, Order)
Hint Text: (None)
Custom Script Code
Local Variables
Nodes = No Point <Point[9][100]>
Node Open? = false <Boolean[9][100]>
Node Closed? = false <Boolean[9][100]>
Picked Node = 0 <Integer>
Path Found = false <Boolean>
HV Score = 10 <Integer>
D Score = 14 <Integer>
G = 0 <Integer[9]>
H = 0 <Integer>
F = 0 <Integer>
Lowest F = 100000 <Integer>
n = 0 <Integer>
Tentative is Better = true <Boolean>
Nodes to Destination = 0 <Integer>
Calculate = 0 <Integer>
Calculate 2 = 0 <Integer>
Path = No Point <Point[100]>
Actions
General - While (Conditions) are true, do (Actions)
Conditions
Path Found == false
(Unit is alive) == true
Actions
Variable - Set Nodes[0][0] = (Position of Unit)
Variable - Set Nodes[1][0] = ((Position of Unit) offset by (0.0, 1.0))
Variable - Set Nodes[2][0] = ((Position of Unit) offset by (1.0, 1.0))
Variable - Set Nodes[3][0] = ((Position of Unit) offset by (1.0, 0.0))
Variable - Set Nodes[4][0] = ((Position of Unit) offset by (1.0, -1.0))
Variable - Set Nodes[5][0] = ((Position of Unit) offset by (0.0, -1.0))
Variable - Set Nodes[6][0] = ((Position of Unit) offset by (-1.0, -1.0))
Variable - Set Nodes[7][0] = ((Position of Unit) offset by (-1.0, 0.0))
Variable - Set Nodes[8][0] = ((Position of Unit) offset by (-1.0, 1.0))
Variable - Set n = 0
General - While (Conditions) are true, do (Actions)
Conditions
Path Found == false
(Unit is alive) == true
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
n > 0
Then
Variable - Set Nodes[0][n] = Nodes[Picked Node][(n - 1)]
Variable - Set Nodes[1][n] = (Nodes[Picked Node][(n - 1)] offset by (0.0, 1.0))
Variable - Set Nodes[2][n] = (Nodes[Picked Node][(n - 1)] offset by (1.0, 1.0))
Variable - Set Nodes[3][n] = (Nodes[Picked Node][(n - 1)] offset by (1.0, 0.0))
Variable - Set Nodes[4][n] = (Nodes[Picked Node][(n - 1)] offset by (1.0, -1.0))
Variable - Set Nodes[5][n] = (Nodes[Picked Node][(n - 1)] offset by (0.0, -1.0))
Variable - Set Nodes[6][n] = (Nodes[Picked Node][(n - 1)] offset by (-1.0, -1.0))
Variable - Set Nodes[7][n] = (Nodes[Picked Node][(n - 1)] offset by (-1.0, 0.0))
Variable - Set Nodes[8][n] = (Nodes[Picked Node][(n - 1)] offset by (-1.0, 1.0))
Else
Variable - Set G[1] = HV Score
Variable - Set G[2] = D Score
Variable - Set G[3] = HV Score
Variable - Set G[4] = D Score
Variable - Set G[5] = HV Score
Variable - Set G[6] = D Score
Variable - Set G[7] = HV Score
Variable - Set G[8] = D Score
Variable - Set Lowest F = 100000
Variable - Set Node Open?[0][n] = false
Variable - Set Node Closed?[0][n] = true
General - Pick each integer from 1 to 8, and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
Node Closed?[(Picked integer)][n] == false
Then
Variable - Set H = ((Integer(((Abs(((X of Nodes[(Picked integer)][n]) - (X of (Target position for Order))))) + (Abs(((Y of Nodes[(Picked integer)][n]) - (Y of (Target position for Order)))))))) * 10)
Debug - Display (Text(H)) as debug output using Type 1, and Do display it in the game window
Variable - Set F = (G[(Picked integer)] + H)
Debug - Display (Text(F)) as debug output using Type 1, and Do display it in the game window
Variable - Set Node Open?[(Picked integer)][n] = true
Variable - Set Tentative is Better = true
Debug - Display (Combine ((Text((Picked integer))), " - ", (Text(F)))) as debug output using Type 1, and Do display it in the game window
General - If (Conditions) then do (Actions) else do (Actions)
If
F < Lowest F
Then
Variable - Set Tentative is Better = true
Variable - Set Lowest F = F
Else
Variable - Set Tentative is Better = false
General - If (Conditions) then do (Actions) else do (Actions)
If
Tentative is Better == true
Then
Variable - Set Picked Node = (Picked integer)
Variable - Set Path[n] = Nodes[Picked Node][n]
Else
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[Picked Node][n] is in (Region((Target position for Order), 1.0))) == true
Then
Variable - Set Path Found = true
Debug - Display "Found !" as debug output using Type 1, and Do display it in the game window
Else
Else
Variable - Modify Nodes to Destination: + 1
Variable - Modify n: + 1
Unit - Order (Triggering unit) to ( Move targeting Path[1]) (Replace Existing Orders)
General - Pick each integer from 2 to (Nodes to Destination - 1), and do (Actions)
Actions
Unit - Order (Triggering unit) to ( Move targeting Path[(Picked integer)]) (After Existing Orders)
things im aware of are
pretty sure im not tracking G correctly.
creating nodes dynamically as they are required. i dont think this is the best way. it also causes a problem where im having overlapping nodes.
i tried making a huge grid of nodes at game init and using those. but i hit the 8192 array limit and although i was able to create a way to find the closest node to triggering unit. i had great difficulty, finding the 8 surrounding nodes and working out which was which.
anyway theres my horrible implementation. i looked at alot of source code that had this crunched down to small blocks but i dont retain enough programming knowledge to properly translate it.
good luck with my mess lol :(
screenshot showing it works with 8 directions now (was only me misscalculating H)
i refered mostly to this guide
http://www.policyalmanac.org/games/aStarTutorial.htm
*EDIT*
just realised i have 2x while loops with indentical conditions. weird. wonder how that happened.
i've gotta goto sleep now. it's really late. or should i say early? 7:30am :<
thanks again for any help you can provide <3
I have no idea what you're doing, but if you can figure this out, I can really use something like it in a map I'm working on now.
Right now I just have a bunch of points telling my units where to go so it is really clunky. I want to come up with some kind of algorithm for the unit's movement and for checking pathing.
Also, What is A* and where can I find out more about it?
@Vortexx2010:
the link at the bottom of my last post describes it in very simple terms
argh, this is too much :<
-
View User Profile
-
View Posts
-
Send Message
Curse PremiumThis isnt entirely accurate, the .grp files themselves store up to 17 frames per side, including North and South, forming up to 32 directions total.
Go play Antioch Chronicles Remastered!
Also, coming soon, Antioch Episode 3: Thoughts in Chaos!
Dont like mapster's ugly white? Try Mapster's Classic Skin!
still trying.
redesigned it again, feels alot closer but wont work out a path if any obstruction. pretty sure im still not counting G properly but all the source code and pseudocode i've looked at hasn't really helped me with that.
this time i have the map attached ready to go
i implemented a visual aid and a 0.0625 delay so you can see it calculate the path as it goes. (it will draw nodes and color them red/green/blue based on nodes current status (open/closed/checking))
hoping someone can help me with this.
resources i used are
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.policyalmanac.org/games/heuristics.htm
http://forum.nystic.com/viewtopic.php?p=76028
pretty please?
worked on it some more
got it finding path around obstacles now
still need help with it however
made a video example !
@maverck: Go
Nice job, it looks good! What else are you trying to find help for on it?
@Jentzsch:
check that my formula is actually correct (i have my doubts even tho it works in the video)
efficiency (is my trigger a piece of shit that runs way slower than it should?)
reconstructing the path (relates to first point. i dont think im setting parent nodes correctly for this.)
group unit movement
best way to implement it.
theres still so very very much i do not know about this system that i need help with.
gawd, what a learning experience. so
feel like i've got the algorithim done finially.
whats left? well it's super super super slow. reading up on this the best way to speed it up seems to be sorting the nodes or a implementing weighted a*
ideally the sorting method if im not too stupid
screenshot for further update...
code in a few posts above can be ignored. code is almost completely different now.
@maverck: Go
Maverck you should release the full algorithm once your done making it efficient as a library, because this could prove very useful for other types of maps.
@ST4RKiLL3R:
yea. i intend to.
community helps me i'll help them ;) lol
anyway, i've got it down, but it needs some serious optimization.
the screenshot below hits the trigger runtime limit of 300-400ms and ends prematurely, the example i've been working off is
http://www.briangrinstead.com/files/astar/
his maxes at about 20ms
i'm pretty sure i know whats causing mine to take so long to run
General - Pick each integer from 1 to (Number of Nodes - 1), and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[(Picked integer)] is in (Region(Picked Node, 1.5))) == true
Closed Nodes[(Picked integer)] == false
so this is a nested loop which picks every node created and checks if it's not closed and is adjacent to the currently selected node
any ideas on how to resolve this?
will probably clean up my trigger abit and comment the hell out of it and post it here later today.
I cant think of a quicker way of doing it atm, but perhaps you can look at the java code of his A* app and see if you can find how he did it. You might be able to implement it in the GE. But IDK if you can read Java. I can't but it might be easier to follow if you know what he's trying to do.
http://www.briangrinstead.com/files/astar/astar.js
Try making a record for each node, with references to all of its neighbors.
Pathfinding 2 Documented
Options: Action
Return Type: (None)
Parameters
Unit = No Unit <Unit>
Source = No Point <Point>
Destination = No Point <Point>
Grammar Text: Pathfinding 2 Documented(Unit, Source, Destination)
Hint Text: (None)
Custom Script Code
Local Variables
path found = false <Boolean>
Picked Node = No Point <Point>
Picked Node Index = 0 <Integer>
New G = 0 <Integer>
Lowest F Node = No Point <Point>
Lowest F Index = 0 <Integer>
new is better = true <Boolean>
Actions
------- Create Starting Node and set H and F Values
Create Node(Source, 0)
Variable - Set H[1] = (Get Dist(Nodes[1], Destination))
Variable - Set F[1] = (G[1] + H[1])
Variable - Set Open Nodes Sorted[1] = 1
Variable - Modify Number of Open Nodes: + 1
Variable - Set Picked Node = Source
------- Initiate main loop
General - While (Conditions) are true, do (Actions)
Conditions
path found == false
Actions
------- create 8 nodes around selected node
------- will not create a new node if another node is already present
General - Pick each integer from 1 to 8, and do (Actions)
Actions
Create Node(Picked Node, (Picked integer))
------- Binary Heap Sorting - Grabs the variable at the top, removes it from the heap and then resorts
Variable - Set Picked Node = Nodes[Open Nodes Sorted[1]]
Variable - Set Picked Node Index = Open Nodes Sorted[1]
Bubble Down()
------- Closes Selected Node
Variable - Set Open Nodes[Picked Node Index] = false
Variable - Set Closed Nodes[Picked Node Index] = true
------- if selected node is destination (path is found) end the main loop
General - If (Conditions) then do (Actions) else do (Actions)
If
(Picked Node is in (Region(Destination, 1.0))) == true
Then
Variable - Set path found = true
Else
------- creates more nodes around currently selected node (might be redundant, or the first one might be, needs checking)
General - Pick each integer from 1 to 8, and do (Actions)
Actions
Create Node(Picked Node, (Picked integer))
------- cause of severe performance loss
------- picks every node and checks if it's adjacent to selected node and not closed
General - Pick each integer from 1 to (Number of Nodes - 1), and do (Actions)
Actions
General - If (Conditions) then do (Actions) else do (Actions)
If
(Nodes[(Picked integer)] is in (Region(Picked Node, 1.5))) == true
Closed Nodes[(Picked integer)] == false
Then
------- Set New G
------- this is the G score of the distance to the current node + the G to get from current node to picked node
Variable - Set New G = (G[Picked Node Index] + (Get G(Picked Node, Nodes[(Picked integer)])))
------- Node is not Open or Closed?
------- Open it.
General - If (Conditions) then do (Actions) else do (Actions)
If
Open Nodes[(Picked integer)] == false
Then
Variable - Set Open Nodes[(Picked integer)] = true
Variable - Set new is better = true
Else
------- if this path is better or first time seeing this node
General - If (Conditions) then do (Actions) else do (Actions)
If
Or
Conditions
G[(Picked integer)] == 0
New G < G[(Picked integer)]
Then
Variable - Set new is better = true
Else
Variable - Set new is better = false
------- path is better, recalculate nodes and set new parent (Parent Node is the node that was used to get to picked node)
General - If (Conditions) then do (Actions) else do (Actions)
If
new is better == true
Then
Variable - Set Nodes Parent[(Picked integer)] = Picked Node
Variable - Set Nodes Parent Index[(Picked integer)] = Picked Node Index
------- H = Distance from picked node to destination
Variable - Set H[(Picked integer)] = (Get Dist(Nodes[(Picked integer)], Destination))
------- G = cost so far to get to this node
Variable - Set G[(Picked integer)] = New G
------- weighted F
------- F typically is G + H, but it's weighted so G + (5 * H)
Variable - Set F[(Picked integer)] = (G[(Picked integer)] + (5 * H[(Picked integer)]))
------- first time seeing this node? add it to the heap and sort
General - If (Conditions) then do (Actions) else do (Actions)
If
Node Seen?[(Picked integer)] == false
Then
Variable - Modify Number of Open Nodes: + 1
Variable - Set Open Nodes Sorted[Number of Open Nodes] = (Picked integer)
Variable - Set Node Seen?[(Picked integer)] = true
Bubble Up()
Else
Else
Else
------- construct path using parent nodes
Reconstruct Path(Unit, Source, Picked Node Index)
Reset Vars()
the record idea is something i've thought about but im not sure how i'll get the index of that node...
*EDIT*
ok after thinking about it for a minute i've come up with the following idea.
when a node is selected it will inherit adjacent nodes from it's parent. it will then check these if they are within a distance. ones too far away will be removed and overwritten with new nodes that are created.
it works in my head. will test it later.
ok.
perfect
got it down significantly
the screenshot i last posted would hit the trigger execution time limit
so thats about 400 nodes
now it takes 41ms to run which is perfect.
now i just have to develop the best way to make units use this.
off the top of my head im thinking of adding units to a variable and have a running thread which picks units from this variable one at a time.
ideas?
Try this:
Events
selected units use move ability
Condition
unit is ground unit = true
Actions
Your Custom Action, with values changed to fit the events and conditions.
Or you could just do one big trigger, with an if then else event covering each ground unit. Make the trigger check to see what unit it is, then follow up with the appropriate action once it's found the unit. This way you aren't running any other actions than you necessarily have to. But you could also just do individual triggers for each unit, and that might give similar results.
41ms is still kind of high isn't it, does it work efficiently enough in-game?
@ST4RKiLL3R:
thats how i had it for testing
but.
that would be 1 thread for every unit
i worry about hitting the thread limit
it's also going to be tricky dealing with unit collision... changing paths... attack move units that acquire targets.