February 1, 2013 at 23:29

Artificial Intelligence. We 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 the plot of films where these same robots capture the world. But there will be artificial intelligence (AI), since AI can be considered present if an evaluation function is used in making the decision. And she will be in our path finding algorithm. And, yes, it will be a simulation of the rescue operation, it will consist in the fact that the rescue team needs to go around all the buildings (all rooms), find people there (which, according to the author’s idea, they themselves cannot escape) and take them out of the building. Everything will be implemented on JavaScipt, Canvas, and a bit of PHP for working with the database. I thought at first to make the article in the style of my last , that is, we are discussing just JavaScript, but I do not want to repeat, so here we will most likely go over the architecture of the program itself (yes, I’ll say right away, if anyone can really wait for the second part of the snake, it’s in the process, I won’t say anything new in the comments on this). With the bureaucracy, everything seems to begin.

    Bit of 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 something like this:
    image

    By the way, the building is real, this is the layout of one of the buildings of my university. Okay, we have a graph to run on. And not just to run, but the shortest ways. This is where our AI comes in. To find the shortest path, the Dijkstra algorithm will be used .On a habr about it many articles, and even several implementations which simplified a lot of work to me. The algorithm is taken out separately, it will receive a graph and an initial vertex at the input - it will return a set of paths to all other vertices. One way is an array of points along which rescuers will run. As we see, we have four exits, that is, logically, rescuers will lead people to the nearest exit. Everything is with theory. Let's get down to practice.

    Implementation


    It will turn out here such a link , but first a few words about the interface:
    - you can change the number of rescuers
    - you can add people (as you want) in the rooms (just click on the room)
    - you can display the graph and vertices (for which you can drag_end_drop)
    - run the button with the appropriate name,
    who read the instructions, click here.

    As we see, I have a lot of buttons at the top (which I commented out so that no one gets anything) They are there to build the graph itself. that is, we click on the scene, add a vertex, then connect the vertices to the edges, then set the outputs (dark green) on the room graph (they will turn dark cherry), we can change the position of the vertex along the way, dragging it when the graph is ready, click save to base. Then, during initialization, the point label and the edge label are counted and a graph is built.
    Points were built using html, but you could make them using the same LibCanvas frameworkfor example, and also draw them on canvas, this would probably be an even more correct solution. But it was done in a way that initially it was not just a point, and there, on a click on it, a settings menu popped up that changed its type, added a person, etc. But the result was redone in a different way. And since this was done on the last night, as always, there was no time to change.
    We will have a class of this point, which will store the coordinates and much more. There will be many points and everyone needs to work somehow conveniently.
    We look at the code
    function PointGR(_data) {    
   this.id = PointGR.setId();   
   PointGR.statArr.push(this);
 }
 PointGR.statArr = []; 
 PointGR.getPointGRById = function(_id) {
    for (var i = PointGR.statArr.length; i--;) {
        if (PointGR.statArr[i].id == _id) {
            return PointGR.statArr[i];            
        }
    }    
    return null;
 }
 PointGR.idPoint = 0;
 PointGR.setId = function() {
    return PointGR.idPoint++;    
 }

    These are the first lines that I write in all classes whose objects will fill arrays (that is, there will be many of them).
    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 a function to which we pass the identifier and it is by it, sorting through the array, it returns the object we need. The function is also static (it is possible or not, that is, to cling to the prototype of the class, but, as practice shows, it is more convenient to static)

    So ... the muse of JavaScript tips has also gone, following the headline muse.
    Although not, it seems to be 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 the static elements on a separate canvas. Which I did. The graph is drawn separately from the running men. At what once. When we start to drag over the peaks - the redrawing is turned on, as soon as we stop - the redrawing is the last time and stops.

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

    Almost 1800 objects, each of which is animated.
    image

    Everything else in the code seems to be obvious and not complicated. Everything is with the code. We proceed to the section "How it works." ("on fingers")

    Section "How it works"


    • 1. None of the rescuers knows where people are, they run around the rooms, and see if there are people there, if any, they are leading them out.
    • 2. Starting from the entrance to the building, each rescuer is given a path along which to run, that is, at point “zero”, the shortest paths are searched from this point to the rooms (more precisely, to all points, this is how the AI ​​algorithm works, but we take only those from them that end with the dot “room”). That is, we take the first path, give it to the first savior, and so on to all. Once the path with the final “room” has been assigned to someone, it falls out of the list of “where to run and see if there are people there”.
    • 3. When the lifeguard came running into the room, the point of the room is checked with the point of the person inside (or near) this room. That is, when we arrange people at the beginning, each person attaches to some point-room (by simply searching for the closest of them all)
    • 4. Okay, he came running, there are people, he takes all the people into an array of his “child” elements, and recounts, again by the AI ​​algorithm, the paths to the exits, takes the shortest of all. Runs to him, dragging people along. Leaves all the people there (at the exit). By the way, someone can recognize the snake in this , and this is it, the same trick.
    • 5. Looks whether there are still unverified rooms (rescuers, according to legend, communicate with each other, so they know which rooms no one has 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 are no people in the 4th point - it checks if there are no checked rooms, if there are - the paths are recounted, runs to them, if there are no more rooms, point 5.
    • 7. It all ends when all the lifeguards left the building.

    Everybody is here. We proceed to the section “A little more about anything”

    A little more about nothing (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 much as you want ) in the rooms (just click on the room)
    - you can display the graph and the vertices (for which drag_end_drop can be used)
    - run 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 delivery as always (a course of logical programming), so the stylization of the code in places is not veryWell, I think that many people have this code when written in the rhythm of the

    PPS “session”. Originally, a two-story building was planned, and a fire. The operation was limited in time (until everything burns out) and in the end people had to jump from the windows. But at the request of the teacher, this was excluded from the task (to jump from the windows). And the meaning of the two floors has disappeared. Buttons for exiting explosions were also made (it caught fire), and rescuers “excluded” him from possible exits and looked for the next. But since he did not manage to debug (once out of four they just ran into the fire) this was excluded from the "final" version.
    Tags:

    Also popular now: