So I talked earlier about my project, but here are the basics. Basically, we have a 2D map which has some objects inside. They can be either walls, which we cannot run over, hospitals, patients, or the player(the ambulance).
So what our algorithm is supposed to do is basically to order the ambulance to move left, right, up or down, and whether to pick up or drop off a patient. So a patient can only exist, in a 2 dimensional matrix, as follows, based on the location of the ambulance: Upper right, Upper left, Lower Right, Lower Left.
So, there can be many ways to reach each patient. First off, we need to locate the patients and add them based on priority to a priority queue and know which patient we need to be going after. Then after finding the best path, since there are walls or non-accessible blocks that can make some paths better, or worse, we need to pick up the patient, then find the nearest hospital, drop the patient off and then find the next one and repeat the process until there are no more patients.
For a static map, meaning where new patients don't come along, it's really easy, and it can be managed by a for loop, since we can count the number of patients. Now, the real challenge is finding the best path to the patient, and then finding the nearest hospital. For this particular project, we assume that the map doesn't change while the game is running. Meaning there won't be any new hospitals, patients or walls or traps.
So the main question is simple, how do we find the best path? And then a bigger question. If we do find a patient, how then do we find the NEAREST hospital? Do we measure all the hospitals' paths and then take the shortest to the closest?
The answer is in graph traversal. If you don't know what a graph or tree traversal is, it basically means to go into a graph, or tree and visit what we see and explain it. Two of the most known traversals are DFS and BFS, which stand for Breadth-First and Depth-First search.
Depth-First Search in this problem, can be the answer, but quite a difficult one, in terms of time complexity, since you have to take all the possible paths and then find the one that has the least amount of depth into the tree. Breadth-First Search now, is quite the opposite. Using a method I like to call Divide & Conquer. So basically, you should think of the whole problem as follows:
- Assume you have multiple rooms, and each room has up to 4 doors, and the minimum number of doors is 1, and you start at one room, and have people go into each possible room.
- Each person that gets to a room, regenerates to the number of doors that said room has, so if a person walks into a room that has 3 more doors, that 1 person would become 3.
- Then each person continues on and leaves footprints until there are no more rooms, and the footprints help the people not go into a room where someone's been before.
Now assume the room that you start at is the starting point, and the room you want to reach has a prize in it. All rooms that can be entered and visited are, therefore you know the location of the prize. You follow the footprints back to the source or the starting point, and there's your best path.
Implementing this using C++ is really easy, and I might share my own source code in a few weeks. Until then, Cheerio!