{"id":43,"date":"2021-11-25T00:49:12","date_gmt":"2021-11-25T00:49:12","guid":{"rendered":"https:\/\/tults.com\/?page_id=43"},"modified":"2021-12-02T04:00:37","modified_gmt":"2021-12-02T04:00:37","slug":"software-engineering","status":"publish","type":"page","link":"https:\/\/tults.com\/index.php\/software-engineering\/","title":{"rendered":"Software Engineering"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Snake<\/h2>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/tults.com\/index.php\/software-engineering\/maze-solving-and-generation\/\">Maze Solving and Generation<\/a><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Synopsis: This project originally started out as a quick and snappy comparison of Dijkstra and A<em>. This however proved difficult, as I had nothing to test it on. As such, I then had to figure out many many other things, starting with, building a maze. I used mazes because I think that they are fascinating, the classic myth of the Minotaur in the labyrinth has always enticed me. So, to test Dijkstra and A<\/em>, I learned how to build a maze. Then, after building mazes, I learned to solve them, and then how to apply other methods of solving, like A* and Dijkstra.<\/p>\n\n\n\n\n<canvas id=\"Maze\" width=\"300\" height=\"300\" style=\"border:1px solid #000000;\"><\/canvas>\n<script>\n\/\/ Function includes all moves made and current tile, is to check to see if there are any white squares around a tile, and is a helper function to get valid moves\nfunction getValidMovesHelper(moves, tile){\n    \/\/Assumes that it is a valid move, then proves otherwise\n    let out = true;\n    \/\/surrounding here is the surrounding moves\n    let surrounding = [];\n    \/\/If there is any surrounding tiles, we push back 1 to surrounding\n    if(moves.includes(tile+20)){\n        surrounding.push(1);\n    }\n    if(moves.includes(tile-20)){\n        surrounding.push(1);\n    }\n    if(moves.includes(tile-1)){\n        surrounding.push(1);\n    }\n    if(moves.includes(tile+1)){\n        surrounding.push(1);\n    }\n    \/\/If there is any more than one item in the surrounding tiles, it is an invalid move, and we return false\n    if(surrounding.length > 1){\n        out = false;\n    }\n    return out;\n}\n\n\/\/ getValid moves, takes a list of all moves, a tile, and a list of all walls and returns all surrounding tiles that it can move to\nfunction getValidMoves(moves, tile, walls){\n    \/\/ Out hereis the output moves\n    let out = [];\n   \n    \/\/Check up\n    if(!moves.includes(tile-1)){\n        if(!walls.includes(tile-1)){\n            if(getValidMovesHelper(moves, tile-1)){\n                out.push(tile-1);\n            }\n        }\n    }\n    \/\/Check Down\n    if(!moves.includes(tile+1)){\n        if(!walls.includes(tile+1)){\n            if(getValidMovesHelper(moves, tile+1)){\n                out.push(tile+1);\n            }\n        }\n    }\n    \/\/Check Left\n    if(!moves.includes(tile-20)){\n        if(!walls.includes(tile-20)){\n            if(getValidMovesHelper(moves, tile-20)){\n                out.push(tile-20);\n            }\n        }\n    }\n    \/\/Check Right\n    if(!moves.includes(tile+20)){\n        if(!walls.includes(tile+20)){\n            if(getValidMovesHelper(moves, tile+20)){\n                out.push(tile+20);\n            }\n        }\n    }\n    return out;\n}\n\n\/\/gen Maze helper loops through the valid moves, and actually implements recursive back tracking\nfunction genMazeHelper(moves, walls){\n    \/\/stacks is the stack of all moves\n    var stacks = [];\n    \/\/ copy all moves into the stack\n    for(i = 0; i < moves.length; i++){\n        stacks.push(moves[i]);\n    }\n    \/\/ declare variables so I don't do it a million times in a while loop\n    var curTile = 0;\n    var allMoves = [];\n    var randNum = 0;\n    var sizeStack = stacks.length;\n    \/\/ While there are moves in the stack, see if there are any valid moves from the top, if there is, make moves until you can't and push to stack and allMoves, then pop until 0. \n    while(stacks.length > 0){\n        sizeStack = stacks.length;\n        curTile = stacks[sizeStack-1];\n        allMoves = getValidMoves(moves, curTile, walls);\n        if(allMoves.length == 0){\n            stacks.pop();\n        }\n        else{\n            randNum = Math.floor(Math.random() * allMoves.length);\n            moves.push(allMoves[randNum]);\n            stacks.push(allMoves[randNum]);\n        }\n    }\n    return moves;\n}\n\nfunction genMaze(){\n    \/\/ Arrays represents maze, size 20*20\n    \/\/ first, fill out maze with Black. \n    let out = [];\n    for(let i = 0; i < 400; i++){\n        out.push(1);\n    }\n    let walls = []\n    \/\/Then fill out the maze. The edges are 0->19; 379->399; 20, 40, 60, 80 so ADD TO LIST\n    for(let i = 0; i < 20; i++){\n        walls.push(i);\n        walls.push(i+379);\n        walls.push(i*20);\n        walls.push(i*20-1);\n    }\n    walls.push(399);\n    \/\/Now draw out start moves\n    let moves = [];\n    moves.push(30);\n    moves.push(31);\n    moves.push(32);\n    moves.push(33, 34, 29, 29);\n    moves.push(51);\n    \n    \/\/Now, we need to generate the rest of the maze!\n    moves = genMazeHelper(moves, walls);\n    \/\/Add entrance\n    moves.push(11);\n    \/\/ Add the exit\n    let validExits = [];\n    for(let m = 360; m < 380; m++)\n    {\n        if(moves.includes(m)){\n            validExits.push(m);\n        }\n    }\n    let randNum = Math.floor(Math.random() * validExits.length);\n    moves.push(validExits[randNum]+20);\n    for(let n = 0; n < moves.length; n++){\n        let cur2 = moves[n];\n        out[cur2] = 0;\n    }\n    return out;\n}\n\n\/\/Init canvas and actually draw\nvar c = document.getElementById(\"Maze\");\nc.parentElement.style.textAlign = \"center\";\nvar ctx = c.getContext(\"2d\");\nlet curMaze = genMaze()\nvar total = 0;\nfor(let i = 0; i < 20; i++){\n   for(let j = 0; j < 20; j++){\n       var val = curMaze[total];\n       if(val != 0){\n           ctx.beginPath();\n           ctx.fillRect(i*15, j*15, 15, 15);\n           ctx.stroke();\n       }\n       total = total + 1;\n   }\n}\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Snake Maze Solving and Generation Synopsis: This project originally started out as a quick and snappy comparison of Dijkstra and A. This however proved difficult, as I had nothing to test it on. As such, I then had to figure out many many other things, starting with, building a maze. I used mazes because IContinue reading &rarr;<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-43","page","type-page","status-publish","hentry","no-thumb"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/pages\/43","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/comments?post=43"}],"version-history":[{"count":4,"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/pages\/43\/revisions"}],"predecessor-version":[{"id":539,"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/pages\/43\/revisions\/539"}],"wp:attachment":[{"href":"https:\/\/tults.com\/index.php\/wp-json\/wp\/v2\/media?parent=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}