We have run into a problem with our AI path finding program. You just need to give us the logic to help us solve the problem, no coding is required at all.
We have an object in a 2D environment that requires to find path and walk, let's call it a "dog"
We also have a function to get dynamic list of rectangles(we know the boundaries of) that represents walkable path on the map, we will call this navrect. This list only covers area with close proximity to the dog, meaning as the dog moves, the list will change.
Right now what we have done is draw all the navrect on a bitmap as white with black background, we will get a map of the surroundings, however note some area are cut off because the navrect will only be shown if the dog walks closer to that area.
We have also wrote function to port the map into 2D array and conduct A* search to find the path from one point to another.
The ultimate problem is how do we tell the dog to explore the entire area in the most efficient way.
What we have tried is use the center of navrect as way points, and use A* to find the distance of each point to the dog and go to point with closest distance. However often the map is big contains hundreads of navrects, A* will take long time to sort all the way points. Even if we can sort way points by distance we do not know the best paths to go through all the waypoints, plus new waypoints that can come up anytime as the dog walk!
Example Map: [url removed, login to view]
We welcome any ideas and questions. The person who can think up the best solution will get $50.
Some clarafication:The navrects do not intersect each other, see http://i.imgur.com/wBETl.jpgJust say the dog is a single pixel and can see things in a radius of 40 pixels/units in 360 degree. You dont have to actually walk to each pixel, but as long as the dog has viewed the area/
or way points within its vision.