\nGame development is one of the important topics in the coding test process utilizing JavaScript. In this course, we will closely examine the process of solving algorithm problems related to game development.<\/p>\n<\/header>\n\nProblem Description<\/h2>\n
This is an algorithm problem that tracks the movement path of game characters.<\/p>\n
Problem:<\/strong> Given a game map, the character starts at (0, 0) and moves to position (n, m). The character can move one step at a time in the upward, downward, left, or right directions, and obstacles are set as impassable tiles. When a map including obstacles is given, find the number of all possible paths for the character to reach the target location.<\/p>\nInput:<\/strong><\/p>\n\n- First line: integers n, m (1 \u2264 n, m \u2264 10)<\/li>\n
- Next n lines: m integers (0 is an empty space, 1 is an obstacle)<\/li>\n<\/ul>\n
Output:<\/strong> The number of paths to the target location<\/p>\n<\/section>\n\nProblem-Solving Approach<\/h2>\n
To solve the problem, we will use the Depth First Search (DFS) method. DFS is effective in exploring all possible paths and counting the number of valid paths. We will proceed with the following steps:<\/p>\n
\n- Initialize the map as a 2D array.<\/li>\n
- Implement a recursive function to explore the path from (0, 0) to (n, m).<\/li>\n
- Stop the exploration when encountering obstacles or boundaries, and count the paths.<\/li>\n
- After exploring all paths, return the number of paths.<\/li>\n<\/ol>\n<\/section>\n\n
Code Implementation<\/h2>\n
Now, based on the above approach, we will proceed with the code implementation using JavaScript.<\/p>\n
\n\nfunction countPaths(map, x, y, n, m) {\n \/\/ If the goal position is reached\n if (x === n - 1 && y === m - 1) {\n return 1;\n }\n \n \/\/ If encountering boundaries or obstacles\n if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {\n return 0;\n }\n \n \/\/ Mark the current position as visited\n const temp = map[x][y];\n map[x][y] = 1; \/\/ Mark as obstacle to indicate visit\n \n \/\/ Move up, down, left, and right\n const paths = countPaths(map, x + 1, y, n, m) +\n countPaths(map, x - 1, y, n, m) +\n countPaths(map, x, y + 1, n, m) +\n countPaths(map, x, y - 1, n, m);\n \n \/\/ Restore the visited position\n map[x][y] = temp;\n \n return paths;\n}\n\nfunction findAllPaths(map) {\n const n = map.length;\n const m = map[0].length;\n return countPaths(map, 0, 0, n, m);\n}\n\n\/\/ Test case\nconst gameMap = [\n [0, 0, 0],\n [0, 1, 0],\n [0, 0, 0]\n];\n\nconsole.log(findAllPaths(gameMap)); \/\/ Output the number of paths\n<\/code>\n<\/pre>\nThe above code calculates the number of paths that can be traversed from (0, 0) to (n-1, m-1) on the game map. It demonstrates well how to handle obstacles and boundaries.<\/p>\n<\/section>\n\nOptimization<\/h2>\n
The implementation above is simple and easy to understand. However, this method may be inefficient due to duplicate explorations. To solve this, we can use memoization techniques. By using memoization, we can save the number of paths that have already been calculated and reuse the stored results when calculating at the same position, improving performance.<\/p>\n
\n\nconst memo = {};\n\nfunction countPathsOptimized(map, x, y, n, m) {\n const key = x + ',' + y;\n \/\/ Check memoization\n if (key in memo) {\n return memo[key];\n }\n \n \/\/ If the goal position is reached\n if (x === n - 1 && y === m - 1) {\n return 1;\n }\n \n \/\/ If encountering boundaries or obstacles\n if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {\n return 0;\n }\n \n \/\/ Mark the current position as visited\n const temp = map[x][y];\n map[x][y] = 1;\n \n \/\/ Calculate paths\n const paths = countPathsOptimized(map, x + 1, y, n, m) +\n countPathsOptimized(map, x - 1, y, n, m) +\n countPathsOptimized(map, x, y + 1, n, m) +\n countPathsOptimized(map, x, y - 1, n, m);\n \n \/\/ Restore the visited position\n map[x][y] = temp;\n \n \/\/ Store in memoization\n memo[key] = paths;\n \n return paths;\n}\n\nfunction findAllPathsOptimized(map) {\n memo = {};\n const n = map.length;\n const m = map[0].length;\n return countPathsOptimized(map, 0, 0, n, m);\n}\n<\/code>\n<\/pre>\nThe optimized code above is almost similar to the previous code, but this time it prevents redundant calculations through memoization. This greatly enhances performance.<\/p>\n<\/section>\n\nConclusion<\/h2>\n
Through this course, we learned how to solve problems related to game development using JavaScript. We learned the basic approach needed to solve problems using DFS and memoization techniques. Practice solving algorithm problems to encounter and tackle more challenges.<\/p>\n
Game development requires creative and logical thinking. By solving various algorithm problems, enhance your coding abilities and apply them to real projects. We will prepare more lectures related to algorithms and game development in the future. Thank you!<\/p>\n<\/section>\n<\/article>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Game development is one of the important topics in the coding test process utilizing JavaScript. In this course, we will closely examine the process of solving algorithm problems related to game development. Problem Description This is an algorithm problem that tracks the movement path of game characters. Problem: Given a game map, the character starts … \ub354 \ubcf4\uae30 “JavaScript Coding Test Course, Game Development”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[141],"tags":[],"class_list":["post-34488","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"\nJavaScript Coding Test Course, Game Development - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34488\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"JavaScript Coding Test Course, Game Development - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Game development is one of the important topics in the coding test process utilizing JavaScript. In this course, we will closely examine the process of solving algorithm problems related to game development. Problem Description This is an algorithm problem that tracks the movement path of game characters. Problem: Given a game map, the character starts … \ub354 \ubcf4\uae30 "JavaScript Coding Test Course, Game Development"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34488\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:28:33+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:41:04+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34488\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34488\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Game Development\",\"datePublished\":\"2024-11-01T09:28:33+00:00\",\"dateModified\":\"2024-11-01T11:41:04+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34488\/\"},\"wordCount\":424,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34488\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34488\/\",\"name\":\"JavaScript Coding Test Course, Game Development - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:28:33+00:00\",\"dateModified\":\"2024-11-01T11:41:04+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34488\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34488\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34488\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Game Development\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"JavaScript Coding Test Course, Game Development - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34488\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Game Development - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Game development is one of the important topics in the coding test process utilizing JavaScript. In this course, we will closely examine the process of solving algorithm problems related to game development. Problem Description This is an algorithm problem that tracks the movement path of game characters. Problem: Given a game map, the character starts … \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Game Development\"","og_url":"https:\/\/atmokpo.com\/w\/34488\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:28:33+00:00","article_modified_time":"2024-11-01T11:41:04+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34488\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34488\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Game Development","datePublished":"2024-11-01T09:28:33+00:00","dateModified":"2024-11-01T11:41:04+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34488\/"},"wordCount":424,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34488\/","url":"https:\/\/atmokpo.com\/w\/34488\/","name":"JavaScript Coding Test Course, Game Development - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:28:33+00:00","dateModified":"2024-11-01T11:41:04+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34488\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34488\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34488\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Game Development"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34488","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34488"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34488\/revisions"}],"predecessor-version":[{"id":34489,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34488\/revisions\/34489"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34488"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34488"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34488"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}