• Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at \$59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.

Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!

### #ActualVildNinja

Posted 05 May 2013 - 04:56 PM

1. Treat each corner, your starting position and the destination as nodes (= 802 nodes).
2. select the starting position
3. find all nodes in direct sight of the current position and add them to the open-list
4. while finding the nodes you should also calculate their price (distance + H) (and perform regular A* stuff - add current node as previous if unvisited or cheaper)
5. jump to cheapest node on the open-list and goto step 3) if this is not the destination.

Since all the rectangles are axis aligned ray tracing shouldn't make that big of an impact, as long as you only move one step at a time (don't calculate the connections between all 802 nodes, only calculate the connections between your current position and all other 801 nodes) assuming you only need 10 steps from end to end, that's ~ 10*801 as compared to 802^2 as I suspect you are doing.

Also don't use a grid. The 802 nodes are the ones you should use

### #3VildNinja

Posted 05 May 2013 - 04:56 PM

1. Treat each corner, your starting position and the destination as nodes (= 802 nodes).
2. select the starting position
3. find all nodes in direct sight of the current position and add them to the open-list
4. while finding the nodes you should also calculate their price (distance + H) (and perform regular A* stuff - add current node as previous if unvisited or cheaper)
5. jump to cheapest node on the open-list and goto step 3) if this is not the destination.

Since all the rectangles are axis aligned ray tracing shouldn't make that big of an impact, as long as you only move one step at a time (don't calculate the connections between all 802 nodes, only calculate the connections between your current position and all other 801 nodes) assuming you only need 10 steps from end to end, that's ~ 10*801 as compared to 802^2 as I suspect you are doing.

Also don't use a grid. The 802 nodes are the ones you should use

### #2VildNinja

Posted 05 May 2013 - 04:38 PM

1. Treat each corner, your starting position and the destination as nodes (= 802 nodes).
2. select the starting position
3. find all nodes in direct sight of the current position and add them to the open-list
4. while finding the nodes you should also calculate their price (distance + H) (and perform regular A* stuff - add current node as previous if unvisited or cheaper)
5. jump to cheapest node on the open-list and goto step 3) if this is not the destination.

Since all the rectangles are axis aligned ray tracing shouldn't make that big of an impact, as long as you only move one step at a time (don't calculate the connections between all 802 nodes, only calculate the connections between your current position and all other 801 nodes) assuming you only need 10 steps from end to end, that's ~ 10*801 as compared to 802! as I suspect you are doing.

Also don't use a grid. The 802 nodes are the ones you should use

### #1VildNinja

Posted 05 May 2013 - 04:36 PM

1. Treat each corner, your starting position and the destination as nodes (= 802 nodes).
2. select the starting position
3. find all nodes in direct sight of the current position
4. while finding the nodes you should also calculate their price (distance + H) (and perform regular A* stuff - add current node as previous if unvisited or cheaper)
5. jump to cheapest node and goto step 3) if this is not the destination.

Since all the rectangles are axis aligned ray tracing shouldn't make that big of an impact, as long as you only move one step at a time (don't calculate the connections between all 802 nodes, only calculate the connections between your current position and all other 801 nodes) assuming you only need 10 steps from end to end, that's ~ 10*801 as compared to 802! as I suspect you are doing.

Also don't use a grid. The 802 nodes are the ones you should use

PARTNERS