En cours

Path Finding Algorithm

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.

Scenario:

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.

Compétences : .NET, Programmation C++, Java, Mathématiques, Robotique

Voir plus : what's an algorithm, what's algorithm, what is the algorithm, what is an algorithm, what is algorithm, what is a algorithm, what an algorithm, what algorithm, use of algorithm, use algorithm, us algorithm, the algorithm is, sort array list in java, sort array c, sort algorithm, solution algorithm, search algorithm in c, search algorithm example, program algorithm example, program algorithm, problem of points solution, problem algorithm, path algorithm, net algorithm, most efficient sort algorithm

Concernant l'employeur :
( 12 commentaires ) Taichung City, Australia

N° du projet : #2370309

Décerné à :

Ashley99

Computational time efficiency.

125 $ USD en 3 jours
(0 Commentaires)
0.0

15 freelance ont fait une offre moyenne de 95 $ pour ce travail

skctechno

I am an expert in C#, VB.NET, So I can do this for you with Quality and Performance. I have 9 years of experience in .Net and this project suits me very well. I complete my projects on or before time, my bid cost i Plus

190 $ USD en 10 jours
(46 Commentaires)
6.2
WebDesignall

HI We can help you Best regards

250 $ USD en 10 jours
(34 Commentaires)
6.4
EngineerCat

I'll talk with you through PM :)

50 $ USD en 0 jours
(5 Commentaires)
4.1
peter100191

I have sent you a description of a solution which I hope will help you.

30 $ USD en 0 jours
(1 Commentaire)
3.4
studioprog

Hi, I have 5 years experience in algorithms and optimization problems. I can do it.

50 $ USD en 1 jour
(7 Commentaires)
3.9
maharshi555

hi, i am no expert in programming, but i am good in reasoning and analyzing. please see PM for an idea which i got.

30 $ USD en 1 jour
(8 Commentaires)
3.0
vernonsullivan

A star should be the most efficient algorithm for this kind of task. If you can, please send me the project for code inspection. Cheers.

50 $ USD en 10 jours
(3 Commentaires)
2.1
Ivanmid

I am working with robot motion planning and simultaneous localization and mapping. See msg for solution.

30 $ USD en 1 jour
(1 Commentaire)
1.2
acadwriting

Hello, i already have a solution for your problem, please check PMB

50 $ USD en 0 jours
(1 Commentaire)
0.0
BlackKnight10

I have the logic and i have just finished the code , been working on that for 2 weeks now , iam ready to send you the algorithm plus the code

200 $ USD en 1 jour
(0 Commentaires)
0.0
mantix

I have the solution and I can make the code in any language you need in 1 day.

90 $ USD en 1 jour
(0 Commentaires)
0.0
digiclay1

Digiclay Has All the Competence & Expertise to Complete the Project in Desired Quality & Time Frame

50 $ USD en 10 jours
(0 Commentaires)
0.0
heerdal

Have experience in shortest path algorithm design. Ready to start

200 $ USD en 10 jours
(0 Commentaires)
0.0
BalintM

Your problem is a well known mathematical one, that has been researched extensively for half a century. Many publications and books discuss many different solutions and algorithms for this scenario, there is no simple Plus

30 $ USD en 2 jours
(0 Commentaires)
0.0