Did you make an H5 game where you wanted to create characters that move to specific positions and avoid walls and obstacles? The following example is implemented by pure JS, drawn by canvas, and only considers moving up, down, left, and right neighborhoods.

Effect display diagram

Have a way to go

No way out

core idea

// Step 1: Draw the checkerboard and extend it one circle
    var $map = drawmap(me.opts, me.$element);
// step 2: draw obstacle points and boundaries, initialize all points, upper left corner is (0,0)
    drawpoint(me, $map);
// By default, the starting point is placed at the checked point
    var startnum = posToindex(me.opts.startY, me.opts.startX, me.opts.mapXnum);
    var endnum = posToindex(me.opts.endY, me.opts.endX, me.opts.mapXnum);
    me.closelist.push(me.wall[startnum]);
// Step 3: Start from the starting point to find the extension point out, up, down, left and right, and record the parent-child point pair. If the point status is 0 and has never been put into OpenList, it is put into OpenList
// Select the set of points with the smallest F value from openList. I made an optimization here, and select the last point in the set to add OpenList to closelist
// From the current detection point and then outward detection, either detect the end point to stop, or wait until all detection points can not find the end point to stop.
    searchroad(me, [me.opts.startY, me.opts.startX], startnum);
// Step 4: Draw all the points for the test, with the thin red line. Just connect the father and son in each fatherson.
    drawroad(me);
// Step 5: Draw the final route, marked with a thick yellow line. Since there is only one parent of a child element, and a parent element has many children (which is difficult to find), we choose to look from the end to the beginning, connecting all the lines that can be connected
    drawFinalRoad(me.fatherson, startnum, endnum, me);Copy the code

I initialized the parameters as follows:

    var me = this;
    // This in the prototype does not refer to the prototype object, but to the call object.
    // Save the length and width of the map
    me.opts = $.extend(true, {}, { // Set popover defaults
        mapXnum: 10.mapYnum: 10.startX: 3.startY: 3.endX: 6.endY: 6.wallnum: 10.map_Per: 40// The length of each grid
    }, options);
    me.wall = [];The coordinates of village boundary and all obstacles are marked 1, start 2, end 3, rest 0, distance left, distance right
    //index from top to bottom, starting at 0, next time try using two-dimensional array... I started with one dimension...
    me.openlist = [];// Point to be detected
    me.closelist = [];// Detected points
    me.fatherson = [];// Record parent-child relationship pairs during the detection process. Record when the parent node looks up, down, left, and right for the child node
    var num = 0;
    for (var i = 0; i < Number(me.opts.mapYnum) + 2; i++) {
        for (var j = 0; j < Number(me.opts.mapXnum) + 2; j++) {
            if (i == 0 || i == Number(me.opts.mapYnum) + 1 || j == 0 || j == Number(me.opts.mapXnum) + 1) {
                me.wall.push({
                    status: 1.pos: [i, j],
                    f_score: 9999.index: num++
                });
            } else if (i == me.opts.startY && j == me.opts.startX) {
                me.wall.push({
                    g_score: 0.status: 2.pos: [i, j],
                    index: num++
                });
            } else if (i == me.opts.endY && j == me.opts.endX) {
                me.wall.push({
                    g_score: 0.h_score: 0.f_score: 0.status: 3.pos: [i, j],
                    index: num++
                });
            } else {
                me.wall.push({
                    g_score: 0.h_score: Math.abs(i - me.opts.endY) + Math.abs(j - me.opts.endX),
                    f_score: 0.status: 0.pos: [i, j],
                    index: num++,
                    inopen: 0}); }}}Copy the code

summary

The way I understand it, Dijkstra’s algorithm is to start at the beginning and spread out around and around until you get to the end, which is slow, but you can still find a shortest path. Intuitively understand how greedy algorithm is the fastest way to solve the problem, the main target is fast, up from mathematical understanding is in when making judgment on the basis of the current optimal solution, every time take is the current position was closest to the finish point, because the algorithm is to take local optimal solution, does not take into account future problems, so on the whole is difficult to find the shortest path. Greed is something everyone has, but enough is enough. Our goal is to find a shortest path at the right speed. Thus, A* algorithm emerged, considering both the starting point and the end point (to select the appropriate heuristic function). After understanding its probably thought, the children shoes people can begin to grope ~~~ hee hee