a-star (Astar, A*) for NXT: RobotC version

[HaWe]

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

[schodet]

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).

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?

[HaWe]

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.

[aswin0]

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!

[physics-matt]

const float E=2.718281828450945235360287471352662497757247093699959574966967627724076630353547594571;

Why all the precision? Most of those digits will get thrown away.

Matt

[HaWe]

[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]

[HaWe]

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!

C and RobotC and NXC don't have booleans.
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.

[physics-matt]

[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]

I did wonder why you didn't use E, but thought it might be because you use that file for other NXC programs.

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

[HaWe]

[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]