Path-finding Webapp Part 1: Front-end

This project was focused around developing a few different algorithms for path-finding. By following a series of directions and rules, an algorithm could search across an area (grid) and find the ending point. This project also focused on the development of an application where a user can create a maze on an interactive grid, choose an algorithm, and send it back for processing. In this post, I discuss the front end features that allow users to create a maze and choose the algorithm to run.


Introduction:

This is a small web application that was designed to showcase a few different path-finding algorithms. The application allows a user to create a maze out of a grid and choose an algorithm to find a path from one end to the other. The project starts with a flask route that creates a numpy array, which is then used in a loop to create a table of cells in the HTML. The table element listens for a mouse down and mouse hover event to change a cell to an active state. The active state simply sets the background color to yellow. Once users have completed their maze, they choose a search algorithm and hit start. A JavaScript function loops through each cell and pushes either a 0 or 1 into a new 2d array. That array is sent back to an endpoint using an Ajax post request. The 2d array is processed concerning the chosen algorithm, and upon the success of the request, a JavaScript function is called to animate the returned values (a visited cell list and pathway list). 


Flask Route:

The flask route that was created for this project was a simple route that only contained a numpy array and a render template for the return value. The numpy array was created as an array of zeros with a width of 30 and a height of 30. This array would be sent to the pathfinding.html file and used to create a table with the same dimensions. 


@application.route("/pathfinding")
def pathfinding():
    cells = np.zeros((30,30))
    search_form = SearchForm()

    return render_template("webapp_templates/pathfinding.html",cells=cells,search_form=search_form)


Font End:

The HTML component of the project would display the grid and necessary buttons or drop-downs for user input. The grid was designed to accept user input through a series of JavaScript functions which would either enable or disable a function for toggling an element to an active state. A function would listen for a mouse enter event and a mouse down event to enable the toggle function and switch a cell to an active state. On the mouse up event, a cell would not toggle even if the user entered it. The actual toggling would either set a cell to an active state or a normal state.


function enableToggle(e) {
  isToggling = true;

  if (e.target !== table) {
    toggle(e);
  }
}

function disableToggle() {
  isToggling = false;
}

function toggle(e) {
  if (isToggling === false) {
    return;
  }

  console.log('toggle:', e.target);

  e.target.classList.toggle('active');
}

function startMaze() {
  table.onmousedown = enableToggle;

  for (var i = 0, il = tableEntry.length; i < il; i++) {
    tableEntry[i].onmouseenter = toggle; //changes color
  }
  table.onmouseup = disableToggle;
}


These states would refer to the CSS, where an active state would have the cell’s background be yellow. The normal state had the background set to white.


.cell.active {
  background-color: #F5F548;
}



Three buttons were created to allow a user to start the process, reset the plot, or restart the app. The start button would initiate a JavaScript function to loop through each cell and push either a 0 or a 1 into a 2d array. If the cell was active, then a 1 would be appended, otherwise, a 0 was appended.


var pathway_selection = document.getElementById("pathway_selection").value;
for (var i = 0; i < rows.length; i++) {
    var nested_array = [];
    for (var j = 0; j < rows.length; j++){
        if (rows[i].cells[j].className == "cell active") {

            nested_array.push(1);
        }
        else {
            nested_array.push(0);
        }
    }
    array.push(nested_array);
}


Once that entire grid was looped through, the array was sent to flask using an Ajax post request. The chosen algorithm name was also sent back in the request. Data sent back was in a JSON format. This data was sent to the endpoint called “pathfinding_receiver”. This was a route created in Flask that would read the request (sent 2d array) and process the data through a chosen algorithm.


$.ajax({
    type:"POST",
    url: "/pathfinding_receiver",
    data : JSON.stringify({'data':array,"algorithm":pathway_selection}),
    contentType: "application/json; charset=utf-8",
    success: function(response) {
        res = JSON.parse(response)
        toggle_loader()
        animatePath(res)
    },
    error: function(error) {
        console.log(error);
    }
});


Once the data has been processed, two lists would be sent back in a JSON format. The lists consist of a visited list and a pathway list. The visited list contains all the cells that were visited and calculated upon. The pathway list consists of all the cells that would be included in the shortest path. Once the data was received, a JavaScript function called animatePath was called. This function would read in the appropriate datasets and call a nested function to iterate over the lists. The nested function takes the visited list data (cell positions) in the list and changes the background to red.


var visited_list = response.visited_list
var path_list = response.path_list
var visited_id = setInterval(pathway_frame,10)
var path_id;
var item = 0
function pathway_frame(){
    if(item >= visited_list.length) {
        item = 0
        path_id = setInterval(shortest_path_frame,10)
        clearInterval(visited_id);
        return null;
    } else {
    rows[visited_list[item][0]].cells[visited_list[item][1]].style.backgroundColor = "red";

    item++;
    }

}


The nested function then takes the data in the pathway list and uses the values to change cells to blue. This would ultimately create a visual of cells that were visited (red) with cells that were found to be included in the shortest path to the end (blue).


function shortest_path_frame(){
    if(item >= path_list.length) {
        clearInterval(path_id);
        return null;
    }else{

        rows[path_list[item][0]].cells[path_list[item][1]].style.backgroundColor = "blue";
        item++;

    }
}



It should be noted that the animation is not in real-time, but rather the results of the processing that went on in the back-end.


The reset button would simply call a JavaScript function to loop through each element, and check if it was active. If it was active, then the element was toggled to a non-active state. Finally, the restart button was created as a simple way to restart the whole process. At the time of this post, this seemed to be the simplest method to restart. In the future, the reset button will be used to completely reset the entire process.A drop-down menu was created to present a user three different options for path-finding. The options consisted of breadth-first search, depth-first search, and A* search. Finally, a drop down was created to allow a user to make changes to the starting and ending nodes. Below is an example of the whole process after creating a maze and choosing the A* algorithm.