-5

I have a project for school that is the following, I have an API structure of an robot in a map with walls and energy stations that were given to me.

What I have to do is to implement the artificial intelligence of the robot so that he can cover the most distance possible in map using the energy stations to recharge energy in the way. The catch here is that the robot when lands on the map doesn't know anything about the map so I go the follow 2d array:

?????????????????????
?????????????????????
?????????????????????
?????????r???????????
?????????????????????
?????????????????????

I can get the initial position, and the heigh and width of the array but I don't know nothing else. Objective of the project is to send the most information about the map.

Can you give some suggestions for were to start, because i've been cracking my head up without finding a solution.

enter image description here

Alexis Pigeon
  • 7,423
  • 11
  • 39
  • 44
user1948423
  • 1
  • Please demonstrate some effort. If you don't know where the start, ponder what might be a good strategy in the beginning, when you know very little about the map. What should your objectives be, and how might you go about achieving them? – NPE Jan 04 '13 at 12:11
  • The two things you say you have access to (init pos, w/h) provide none of the information that you need. You clearly must have a better API (how many blocks you can "see", the directions you can move, etc) and have simply failed to describe it well. – Steven Lu Jan 04 '13 at 12:12
  • This is not a programming question, this is a how-do-i-approach-a-problem question. Your job as a student is to figure this out for yourself! – Dave Jan 04 '13 at 14:09

2 Answers2

2
  1. Move the Robot around the map to discover new tiles
  2. Implement Pathfinding in order to calculate the distance to nearest energy station
  3. Move back nearest energy station if fuel = distance to nearest energy station
  4. Explore every tile
Sven
  • 2,839
  • 7
  • 33
  • 53
  • Thank you very much. But one more question the exploration of the tiles there's any algorithm that i can use that can help me with that? – user1948423 Jan 04 '13 at 12:14
  • you just have to make sure to explore every node. Going node by node in specific order. – jellyfication Jan 04 '13 at 12:16
  • @user1948423 http://stackoverflow.com/questions/8964966/a-i-that-can-navigate-a-randomly-generated-2d-city?rq=1 – Sven Jan 04 '13 at 12:17
  • How do i specify the order since the robot does not know anything? – user1948423 Jan 04 '13 at 12:17
  • He can compute how many exits he has from current tile and always take lets say the right, up, left, down respectivly if available. When he does that with every tile he eventualy discovers whole map. – jellyfication Jan 04 '13 at 12:19
  • You know your location, you probably know the tiles around you and you know the type. Thats all you need. We don't know your API, so specific help is difficult. – Sven Jan 04 '13 at 12:19
  • ok thanks anyway you've much helpful – user1948423 Jan 04 '13 at 12:20
0

Since you have no information to start with, it would seem a simple depth-first search would be in order since. I would suggest checking google for some information about recursive depth-first searches.

Mike
  • 2,434
  • 1
  • 16
  • 19