Artificial Intelligence. Simulate a rescue operation

Perhaps the headline is too flashy, the muse on the headlines left me. And, yes, there will be no Japanese robots and a plot of films where these same robots take over the world. But there will be artificial intelligence (AI), since AI can be considered present if an evaluation function is used when making a decision. And it will be in our pathfinding algorithm. And yes, it will be a simulation of a rescue operation, it will be that the rescue team needs to go around all the buildings (all the rooms), find people there (who, according to the author, cannot escape themselves) and take them out of the building. Everything will be implemented on JavaScipt, Canvas, and some PHP for working with the database. I thought at first to make an article in the style of my last , that is, we are discussing exactly JavaScript, but I don’t want to repeat it , so here we’ll most likely go over the architecture of the program itself (yes, I’ll tell you if someone can really wait for the second part of the snake, it is I will not say anything new about this in the comments). With bureaucracy, it seems, everything, let's get started.

Some theory

What do we need to do? We will have a graph, that is, all the control points of the building, on which our people will run. It will look like this:


By the way the building is real, this is the layout of one of the buildings of my uni. Okay, we have a graph for which to run. What has not just run, and the shortest paths. This is where our AI comes in. Dijkstra’s algorithm will be used to find the shortest path . On Habré about him a lot of articles, and even a few implementations that I have simplified a lot of work. The algorithm is taken out separately, the input will be the graph and the initial vertex - the set of paths to all the other vertices will return. One way is an array of points along which rescuers will run. As we see, we have four exits, that is, it is logical that rescuers will lead people to the nearest exit. With theory everything. Let's start to practice.

Implementation

Here we have a link , but first a couple of words about the interface:
- you can change the number of rescuers
- you can add people (as you like) to the rooms (just click on the room)
- you can display a graph and vertices (for which you can drag_end_dropit)
- we start by the button with the corresponding name
who read the instructions click here
')
As you can see, I have a lot of buttons up there (which I commented so that no one gets anything wrong ). They are there to build the graph itself. that is, we click on the stage, add a vertex, then connect vertices into edges, then expose the room graph (they will turn green), exits (dark cherry), we can change the vertex position along the way, dragging it when the graph is ready - click save to base. Then, during initialization, the plate of points and the plate of edges are counted and a graph is constructed.
The points were built by means of html, but you could make them using the same LibCanvas framework , for example, and also draw them on the canvas, it would probably be a better solution. But it was done the way it was originally not just a point, and there, on clicking on it, a menu of settings fell out, which changed its type, added a person, etc. But the result was redone differently. And since it was done on the last night, as always, there was no time to change.
We will have the class of this point, which will store the coordinates and whatnot. There will be a lot of points and it’s convenient to work with these all.

These are the first lines that I write in all classes whose objects will fill in arrays (that is, there will be many).
1. We put a unique identifier. This is done (logically) through a static field.
2. In the constructor, add each newly created object to the static array.
3. We write the function to which we pass the identifier and it, by scanning the array, returns the object we need. The function is also static (it is possible and not, that is, to cling to the class prototype, but, as practice shows, static is more convenient)

So ... the muse of tips on javascript is also gone, following the muse by headlines.
Although no, it seems still here. You can still say about optimization. Initially, everything was on the same canvas and each frame was redrawn. But when viewing the CPU load while displaying the graph, logical conclusions were made and changes were made.

We take out all static elements on a separate canvas. What I did. The graph is drawn separately from the running man. With that one time. When we start dragging over the vertices, the redrawing is turned on as soon as we stop - the last time is redrawn and stops.

On a large number of people (and these are all objects of classes, and by the way they are still physical bodies (on the same engine that they wrote recently), but in this case with the collision turned off), of course, lags are noticeable, unfortunately.
Here, I kind of scored all the rooms with people.


Almost 1800 objects, each of which is animated.


Everything else on the code seems to be obvious and not difficult. With the code all. We proceed to the section "How it works." ("on fingers")

Section "How it works"

• 1. None of the rescuers know where people are, they run around the rooms, and see if there are people there, if there are people leading them to the exit.
• 2. Starting from the entrance to the building, each rescuer is given the path to run, that is, at the “zero” point, the shortest paths from this point to the rooms are searched (more precisely, to all points, this is how the AI ​​algorithm works, but we take only those that end with a dot “room”). That is, we take the first path, give it to the first rescuer, and so on to all. As soon as the path to the final “room” was assigned to someone, it drops out of the list “where you need to go in and see if there are any people there”.
• 3. When the rescuer ran into the room, the point of the room is checked with the person’s point inside (or close) to that room. That is, when we arrange people at the beginning, each person is attached to some point-room (by simply searching for the closest one)
• 4. Okay, come running, there are people, takes all people into an array of their “child” elements, and recalculates, again the AI ​​algorithm, the path to the exits, takes the shortest of all. Runs to him, pulling people along. Leaves all people there (at the exit). By the way, someone can learn this snake , but this is it, the same technique.
• 5. Looks to see if there are still untested rooms (the rescuers, according to legend, communicate with each other, therefore they know which rooms have not been visited yet), if they stayed, again, from the current point, there is the shortest path to the rooms. If there are no more rooms, it remains at the exit.
• 6. If there were no people in the 4th point - if there are any rooms that have not been checked, if there are, then the paths are recalculated, runs to them, if there are no more rooms, point 5.
• 7. Everything ends when all the rescuers leave the building.

Everybody is here. Go to the section "A little more about anything"

A little more about anything (no, there will be no title)

I repeat, so as not to scroll up: A few words about the interface:
- you can change the number of rescuers
- you can add people (as you like) to the rooms (just click on the room)
- you can display a graph and vertices (for which you can drag_end_dropit)
- we start by the button with the corresponding name
To try click here .
Files can be taken by clicking here .

PS It was done on the last night before the change as always (logic programming course), so the stylization of the code is not well, in some places I think, many people have such code when written in the rhythm of the “session”

PPS Originally planned two-story buildings, and fire. The operation was limited in time (until everything burned down) and at the end people had to jump from the windows. But at the request of the teacher, it was excluded from the task (to jump from the windows). And the meaning of the two floors disappeared. But buttons of explosions of an exit were made (he caught fire), and rescuers "excluded" him from possible exits and looked for the following. But since he did not have time to debug (once out of four they just ran into the fire) this was excluded from the "final" version.