NXC: astar (A* a-star AStern): pathfinding for NXT in a maze
Posted: 08 Jun 2011, 18:33
Hi,
this is the improved a-star (Astar, A*) version for NXC (Bricxcc 3.3.10.x, enhanced firmware 1.28).
At the start you'll see a map of about 45x45 single square fields, coordinate origin (0,0) is in the center.
If you define each of the square fields e.g. by 40-50cm edge length (each field should be at least as big as the robot itself) you'll have a labyrinth of about 400 m² to explore. :)
For testing, some walls and a start and a destination point are already predefined.
The starting point is quite in the left middle area, the destination point is at the right edge.
The searching starts backwards from destination to departure (because of code optimization reasons).
You can watch the "cloud" of expanded nodes "roll" over the display, as the program calculates the shortest route.
When the cloud of nodes has reached the start reversely, the calculated shortest way will be displayed several times (for demonstrating) on the screen with additional routing advices.
This algorithm is planned to work with my navigation robot in future, which will enable him e. g. to drive around and explore and solve mazes.
(provided good encoders for odometry)^^
This is the new code, hopefully even a little less faulty^^
share and enjoy!
:)
http://www.mindstormsforum.de/viewtopic.php?f=70&t=6619
this is the improved a-star (Astar, A*) version for NXC (Bricxcc 3.3.10.x, enhanced firmware 1.28).
At the start you'll see a map of about 45x45 single square fields, coordinate origin (0,0) is in the center.
If you define each of the square fields e.g. by 40-50cm edge length (each field should be at least as big as the robot itself) you'll have a labyrinth of about 400 m² to explore. :)
For testing, some walls and a start and a destination point are already predefined.
The starting point is quite in the left middle area, the destination point is at the right edge.
The searching starts backwards from destination to departure (because of code optimization reasons).
You can watch the "cloud" of expanded nodes "roll" over the display, as the program calculates the shortest route.
When the cloud of nodes has reached the start reversely, the calculated shortest way will be displayed several times (for demonstrating) on the screen with additional routing advices.
This algorithm is planned to work with my navigation robot in future, which will enable him e. g. to drive around and explore and solve mazes.
(provided good encoders for odometry)^^
This is the new code, hopefully even a little less faulty^^
share and enjoy!
:)
http://www.mindstormsforum.de/viewtopic.php?f=70&t=6619