Printable View
hi, I gotta robot i am working on programming, this robot can go F/B L/R U/D and plots its location, along with the obstacles it detects.
However I need help with an algorithm that can store the coordinates of obstacles... recall them, and calculate which the shortest distance is to take.
I am writing this in basic, but any assistance could help.
THNX!
I moved your thread here from the VB6 forum because while you may not be writing a game, you probably have a better chance of getting help here. I'll move it back it if want.
no thats ok! any help is great!!!!
There are several path finding algorithms out there and maybe one or two described in this forum. Try giving the forum a quick search for key terms: Path finding. You'll most likely look at Dijkstra, Floyd & A* (A-Star) from easiest to hardest IMO.
You didn't mention whether or not the robot's field is tiled or not. You'll have to do some research into the different algorithms unless you can find a class/project already written for you.
Regarding the obstacles, if your field is tiled, store the obstacles using a class or UDT (user-defined type) that includes the "tile start" and "tile stop" numbers. From those you can calculate the total rectangle of the obstacle or simply store the obstacles as rectangles. With regards to recalling them later, maybe use a simple text file to store that tile/obstacle information.
I'm not suggesting, nor supporting, the unique method I developed (posted on planetsourcecode). But it was used by a coder for his robot. You can find other pathfinding projects on that site also.
I helped someone else with a similar project once long ago back in college. He implemented the Dijkstra algorithm for his code, but the hardest thing was upon detection of obstacles, for the robot to do boundary detection. I'm assuming this is just a simple floor crawling robot with a bumper to detect obstacles while it explores it's environment.
The problem was, when it hits an obstacle, how does it know if it's something simple like a post, something larger like a box or something like a wall (a plane that extends). He wrote routines for having the robot figure out the details of each of these cases as it built it's internal map of the world. As the robot explored it's world, it would seed it's world-space with nodes for a navigation network.
Once it had the nodes, then in came the Dijkstra method to navigate around the world-space. You told the robot a coordinate, and it would first move to the closest node in it's node-path structure, then follow the node-structure according to Dijkstra to the node closest to the destination coordinate point. Finally, it would move off the node-structure to the coordinates in a simple straight-line.
Later, he implemented where if the robot was told to move to a coordinate in "unexplored" area, it would move through it's node-network to the edge of it and then go into exploration mode as it tried to make it's way to the location; adding new nodes to it's Dijkstra network as it went.
As I recall, it wasn't hard to implement. We programmed it in ANSI C back in the day but I suspect with the object-orientedness of VB.NET, it would be far simpler now.
alright! that's a cool little program foxy!@ I spent almost an hour playing with it. However could you please extract the line(s) for me that actually does the calculation. I was reading the dike-strak code and if thats the easy one im in trouble!
In regards Jenner, to my sensors 2 are IR(go up to 10cm)on the sides, and one ultrasonic(1m) in front, I am planning to use a square block map, (if thats what we mean by tiled), this will also keep it a good distance from collisions, since i am not writing 0's for the empty blocks.
just reading both your hints I am slowly devising a plan....
what i am thinking of is where:
robot starts on a blank map,, and heads for target co-ordinates, upon INITIAL arrival of first object detection(prolly@front end) robot will plot coordinates, after that it will try to go around...say left,,,, (shortest distance routine) , but as it tries to go around it will hit another response in object sensor, , use SDR(short distance routine), since only 2 points will be on map(initial and current, and around current is shortest), the SDR will tell it to keep going, since it is always the shortest route(in known memory), this will maintain that it keeps going around in the same direction until it goes past object
The Second time I launch (from the same start spot) It will again head for the initial object, but this time as it approaches object it will recall map from last trip, remember that there are objects in front and to left which would make right now the short distance, so it would then continue right, plot more mapping and continue around .......
The third time around it now has all the data and can make proper(accurate) decision.
Also I was reading about x-y maps for greyscale graphics, and i think this is the way to go, and just plot maximum heights, although its less accurate, it wont try to go under things and get stuck.
This will be my map which i will try to do in a txt file on my SD card(as advised)
.....but where do i find command strings to read fat32, open the file and write the file? Also how do I count down 36lines and over 27,to get my plot? (i am using SPI btw,, so i think its the same as a serial comm)
and did I mention this is all in BASIC, since it was the closest HEX compiler to VB...
If your field is tiled (squares), you may wish to look at A-star. My unique implementation was for non-tiled fields. In the Games portion of the forum, there is a VB-written A-star project you might be able to adapt.