a-star (Astar, A*) for NXT: RobotC version
a-star (Astar, A*) for NXT: RobotC version
One of my projects I've been doing lately: an a-star (Astar, A*) algorithm for NXT, RobotC version
It uses an a-star algorithm, modified by Dijkstra (the estimated distance to destination is always =0; this simplifies the node structure, enlarges the possible size of the map and accelerates the execution speed).
(You'll need in addition the file RobotC+.h, see below)
http://www.robotc.net/forums/viewtopic.php?f=15&t=456
It uses an a-star algorithm, modified by Dijkstra (the estimated distance to destination is always =0; this simplifies the node structure, enlarges the possible size of the map and accelerates the execution speed).
(You'll need in addition the file RobotC+.h, see below)
http://www.robotc.net/forums/viewtopic.php?f=15&t=456
Last edited by HaWe on 09 Jun 2013, 15:54, edited 5 times in total.
Re: a-star (Astar, A*) for NXT: RobotC version
Actually, if I am not wrong, running a A* without the heuristic is the Dijkstra algorithm, and will never be better than the same algorithm using the heuristic. Can you explain more?doc-helmut wrote:It uses an a-star algorithm, modified by Dijkstra (the estimated distance to destination is always =0; this simplifies the node structure, enlarges the possible size of the map and accelerates the execution speed).
LEGO things http://ni.fr.eu.org/lego/ - NXT Improved Firmware (GCC) http://nxt-firmware.ni.fr.eu.org/ - Other robots http://apbteam.org
Re: a-star (Astar, A*) for NXT: RobotC version
I started using the heuristic, but this needed too much variable memory (and a little more calculating time).
so I compared the results of pathfinding both with and/or without heuristic and found that the results were quite the same.
Even if there should be one ore two examples where the heuristic probably might be a little more efficient (though I didn't find any so far), I sacrificed that approach and further worked along without heuristic - and enlarged the possible size of the map by that and increased the execution speed a a little.
so I compared the results of pathfinding both with and/or without heuristic and found that the results were quite the same.
Even if there should be one ore two examples where the heuristic probably might be a little more efficient (though I didn't find any so far), I sacrificed that approach and further worked along without heuristic - and enlarged the possible size of the map by that and increased the execution speed a a little.
Re: a-star (Astar, A*) for NXT: RobotC version
I noticed that your maps are arrays of shorts but contain only Boolean values. Maybe converting them to booleans could save memory space and increase speed. ( unless robotc stores booleans as shorts inernally)
Nice work!
Nice work!
My blog: nxttime.wordpress.com
-
- Posts: 76
- Joined: 29 Sep 2010, 06:57
Re: a-star (Astar, A*) for NXT: RobotC version
Why all the precision? Most of those digits will get thrown away.doc-helmut wrote: const float E=2.718281828450945235360287471352662497757247093699959574966967627724076630353547594571;
Matt
Re: a-star (Astar, A*) for NXT: RobotC version
[OT] @physics-matt:
though your questioin is OT - here's my OT answer:
it was just a joke - I didn't even need this for this astar program as you could have noticed *ggg*
[/OT]
though your questioin is OT - here's my OT answer:
it was just a joke - I didn't even need this for this astar program as you could have noticed *ggg*
[/OT]
Last edited by HaWe on 01 Oct 2010, 15:57, edited 1 time in total.
Re: a-star (Astar, A*) for NXT: RobotC version
C and RobotC and NXC don't have booleans.aswin0 wrote:I noticed that your maps are arrays of shorts but contain only Boolean values. Maybe converting them to booleans could save memory space and increase speed. ( unless robotc stores booleans as shorts inernally)
Nice work!
if there's a definition for booleans, it's actually char.
But RobotC was for a very long time bugged like hell when calculating with chars (and BTW using floats within structs) , so I had to take short at this place.
But RobotC I don't use at all any longer. This code above is more then 2 years old, the current code which I'm using is the NXC version.
-
- Posts: 76
- Joined: 29 Sep 2010, 06:57
Re: a-star (Astar, A*) for NXT: RobotC version
I did wonder why you didn't use E, but thought it might be because you use that file for other NXC programs.doc-helmut wrote:[OT] @physics-matt:
though your questioin is OT - here's my OT answer:
it was just a joke - I didn't even need this for this astar program as you could have noticed *ggg*
[/OT]
Although, I must admit that it doesn't seem very sensible to declare a global variable called E for no reason.
But anyway, sorry to go off topic by actually commenting on your code (Glad to see nothing changes )
Matt
Re: a-star (Astar, A*) for NXT: RobotC version
[OT] yes, some things remain the same.
BTW, you actually didn't comment the topic (my a* code) but "off-topically" the second-rated detail about an apparently unnecessary precision of an unused variable in an outdated second-rate header file. It would actually be unnecessary at all to say a single word about it, but who studied long enough will, of course, always find a fly in the soup (at least a second-rated fly) ;) (excuse my GEnglish) [/OT]
BTW, you actually didn't comment the topic (my a* code) but "off-topically" the second-rated detail about an apparently unnecessary precision of an unused variable in an outdated second-rate header file. It would actually be unnecessary at all to say a single word about it, but who studied long enough will, of course, always find a fly in the soup (at least a second-rated fly) ;) (excuse my GEnglish) [/OT]
Who is online
Users browsing this forum: No registered users and 0 guests