{"id":498,"date":"2013-04-28T23:31:02","date_gmt":"2013-04-28T22:31:02","guid":{"rendered":"http:\/\/www.radicalfishgames.com\/?p=498"},"modified":"2013-05-05T11:28:37","modified_gmt":"2013-05-05T10:28:37","slug":"path-finding-in-crosscode","status":"publish","type":"post","link":"https:\/\/www.radicalfishgames.com\/?p=498","title":{"rendered":"Path Finding in CrossCode"},"content":{"rendered":"<p>The path finding algorithm of CrossCode was just recently developed, but works already fairly well. Overall, we\u2019re pretty enthusiastic about the result. That\u2019s why we\u2019re happy to answer your requests to share some of the ideas and optimizations behind this new feature.<\/p>\n<p>For starters, we have a short video demonstrating the overall performance of the path finding and the underlying data structures.<\/p>\n<p><iframe title=\"CrossCode: Path Finding Preview\" width=\"600\" height=\"338\" src=\"https:\/\/www.youtube.com\/embed\/J7mFjlyScHA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>If you find those results convincing, here is how we did it:<\/p>\n<h2>Requirements on the path finding<\/h2>\n<p>Let\u2019s first talk about what we wanted to achieve with path finding.<\/p>\n<ol>\n<li>Entities should navigate to the target <strong>efficiently<\/strong> (close to shortest route), even in complex environment<\/li>\n<li>Entities should be able to navigate over <strong>different height levels<\/strong> of the map. (e.g. jump on container, jump from one container to the other and down again)<\/li>\n<li>The navigation should work in <strong>real-time<\/strong> and fast enough to be recalculated repeatedly.<\/li>\n<\/ol>\n<p>The default solution to finding the optimal path to a target in an arbitrary complex environment is the <a href=\"http:\/\/en.wikipedia.org\/wiki\/A*_search\" target=\"_blank\">A* search algorithm<\/a>.<\/p>\n<h2>Optimized Navigation Map<\/h2>\n<p>The performance of the A* search algorithm heavily depends on the choice of graph structure it is applied on. We do not simply use a tile structure (e.g. the collision map) for this, mostly for performance reasons (one node per tile means a LOT of nodes). Instead, we created an optimized structure, which we call <strong>NavMaps<\/strong>. We already discussed these structures (and how they are created in the level editor) in a <a href=\"http:\/\/www.radicalfishgames.com\/?p=186\">previous weekly report<\/a>.<br \/>\nNodes of our NavMaps cover multiple tiles and are connected with all adjacent nodes (called neighbor nodes). For each neighbor node, we also store all the edges where the nodes touch exactly. The perfect shape for a NavMap node is a large rectangle.<br \/>\nHere an up-to-date visualization of a NavMap in-game.<\/p>\n<p><a href=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/overview.png\"><img decoding=\"async\" class=\"aligncenter size-medium wp-image-501\" alt=\"overview\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/overview-300x200.png\" width=\"300\" height=\"200\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/overview-300x200.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/overview-450x300.png 450w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/overview.png 960w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<h2>Performing the A* Search<\/h2>\n<p>To find out how the A* Search works in general simply check out the <a href=\"http:\/\/en.wikipedia.org\/wiki\/A*_search\">wiki article<\/a>. We use the algorithm exactly as described on that page. There a just two functions that we should explain in more detail:<\/p>\n<dl>\n<dt>heuristic_cost_estimate(node, goal)<\/dt>\n<dd>This function should estimate the cost to go from node to goal<\/dd>\n<dt>dist_between(node1, node2)<\/dt>\n<dd>This function should compute the cost to travel from node1 to node2<\/dd>\n<\/dl>\n<p><strong>Here is the important thing:<\/strong> At first we were lazy and simply implemented these functions my measuring the <strong>distance from the center\u00a0of the nodes<\/strong>.<\/p>\n<p>And here is why this\u00a0doesn&#8217;t\u00a0work:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-506\" alt=\"optimal_route_1\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_1.png\" width=\"600\" height=\"345\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_1.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_1-300x172.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_1-500x287.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>How do we reach our target (red point)? Simply go over node 5 and 8, right?<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-507\" alt=\"optimal_route_2\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_2.png\" width=\"600\" height=\"345\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_2.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_2-300x172.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_2-500x287.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>Wrong! By measuring the distance from the center of all the nodes, it seems shorter to take the path over node 6. This is obviously not the shortest path, though.<\/p>\n<p><strong>How to do it better<\/strong>: instead of measuring from the center of each node, we measure from the <strong>point on which we enter the node<\/strong>. We approximate this point by taking the average position of the edges between the nodes.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-508\" alt=\"optimal_route_3\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_3.png\" width=\"600\" height=\"345\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_3.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_3-300x172.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/optimal_route_3-500x287.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>This way, the heuristic works much better with our NavMap structure.<\/p>\n<h2>Moving between nodes<\/h2>\n<p>With our A* search performed we get a list of nodes we need to traverse to get to our target. However, we\u2019re not quite done yet. Since our nodes tend to be large and connected via multiple edges the next question is: <strong>How exactly do we go from one node to the other<\/strong>?<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-509\" alt=\"between_nodes_1\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_1.png\" width=\"600\" height=\"343\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_1.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_1-300x171.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_1-500x285.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>Our plan here is to go to our target (red point, again) crossing node 12. Going from node 6 to 12, we can choose among 3 edges to cross. Between node 12 and 15, we have exactly one very wide edge. So we need to determine two things:<\/p>\n<ol>\n<li>On which <strong>edge <\/strong>between the nodes do we cross?<\/li>\n<li>On which <strong>point <\/strong>on the edge to we cross?<\/li>\n<\/ol>\n<p>The first approach we took: Let\u2019s cross the edges on the point that is <strong>closest to the current position<\/strong>. However, this doesn\u2019t work too well in this case:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-510\" alt=\"between_nodes_2\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_2.png\" width=\"600\" height=\"343\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_2.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_2-300x171.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_2-500x285.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>The next idea: Cross edges and points <strong>closest to the target<\/strong>.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-511\" alt=\"between_nodes_3\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_3.png\" width=\"600\" height=\"343\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_3.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_3-300x171.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_3-500x285.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>This works much better already, but still not that optimal. The best solution we found so far is to cross the edge and point <strong>closest to the line between the current position and the target<\/strong>:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-512\" alt=\"between_nodes_4\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_4.png\" width=\"600\" height=\"343\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_4.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_4-300x171.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/between_nodes_4-500x285.png 500w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>This option provides the path closest to the optimal solution (which is the straight line to the target). In case you wonder why we always cross orthogonally over edges: this makes the path finding more stable for complex routes.<\/p>\n<h2>Moving over multiple levels<\/h2>\n<p>As we mentioned before, an important requirement for our path finding is navigation over multiple heights. Entities can jump on higher platforms, from one platform to another and fall down. All these options should be considered in our path finding as well.<\/p>\n<p>You might have noticed that jumping for the player in CrossCode is pretty much automatic: you just move toward an edge to fall down or jump to another platform, or you move toward a wall to jump up. Using such an automatic jumping system makes path finding with jumping fairly simple: we only need to find a path that leads the entity toward the right walls and edges \u2013 the jumping happens automatically.<\/p>\n<p>To make all this work, we first need to expand our NavMap to all height levels. Let\u2019s start with the ground level:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-513\" alt=\"map-comparison-1\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-1.png\" width=\"600\" height=\"531\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-1.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-1-300x265.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-1-338x300.png 338w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>Here we specify nodes only for the ground level, ignoring the top of the containers. We connect those nodes to the upper level, by mapping arrow symbols next to them. We obviously do this only where it is possible to jump up (e.g. nearby conveniently places cardboard boxes). Edges touching the arrow symbols are stored as \u201c<strong>jump-up-edges<\/strong>\u201d (visible in white) and connect to nodes of the upper level.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-514\" alt=\"map-comparison-2\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-2.png\" width=\"600\" height=\"531\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-2.png 600w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-2-300x265.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/map-comparison-2-338x300.png 338w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<p>And here we have the NavMap of the upper layer, where we do not only specified nodes on top of containers, but also on the empty space between containers \u2013 the space that can be crossed by jumping. The nodes over empty space are called <strong>AirNodes<\/strong> and are handled a bit differently from normal nodes. We ignore AirNodes during the A* Search. Instead, we connect all neighbours of an AirNode directly with each other, storing additional information such as jump distance. That way, we can correctly decide, if an entity can actually cross an AirNode by jumping (not all entities will be able to jump the same distance).<br \/>\nAs for all the white edges that you see on the right half: this time they are \u201c<strong>jump-down-edges<\/strong>\u201d that lead back to the lower level. Those edges are computed automatically and don\u2019t require any special tiles.<\/p>\n<h2>Let&#8217;s jump!<\/h2>\n<p>Now we got our NavMap extended to all levels. The Path-Finding algorithm is exactly the same as before, it only includes the nodes of all levels. So let\u2019s say we want our protagonist to move to a target (red point) on top of a container like so:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-515\" alt=\"jump-navi-1\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-1.png\" width=\"588\" height=\"480\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-1.png 588w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-1-300x244.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-1-367x300.png 367w\" sizes=\"(max-width: 588px) 100vw, 588px\" \/><\/p>\n<p>Running the same algorithm as before we get the following path:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-516\" alt=\"jump-navi-2\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-2.png\" width=\"588\" height=\"480\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-2.png 588w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-2-300x244.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/jump-navi-2-367x300.png 367w\" sizes=\"(max-width: 588px) 100vw, 588px\" \/><\/p>\n<p>Note that the dark red line shows the path on ground level (we really don\u2019t consider height for the path-finding at all). The lighter red line is the path correctly mapped to the upper level.<\/p>\n<p>And this works! By simply moving across the lower white edge we jump up the container, moving across AirNode 19, leading us to jump all the way to our target.<\/p>\n<p>Obviously our AI-controlled mouse friend can now do exactly the same:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-517\" alt=\"mouse-follow-1\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-1.png\" width=\"502\" height=\"285\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-1.png 502w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-1-300x170.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-1-500x283.png 500w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/p>\n<p>Oh the wonders of technology!<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-518\" alt=\"mouse-follow-2\" src=\"http:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-2.png\" width=\"502\" height=\"285\" srcset=\"https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-2.png 502w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-2-300x170.png 300w, https:\/\/www.radicalfishgames.com\/wp-content\/uploads\/mouse-follow-2-500x283.png 500w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/p>\n<p>Well, F***!<\/p>\n<p>This concludes our technical post about path finding. I hope some of you can take a few good ideas from that. There are obviously a lot of more details to be considered, but this pretty much covers the basic algorithm.<\/p>\n<p>Any feedback or questions? Comments are below as usual!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The path finding algorithm of CrossCode was just recently developed, but works already fairly well. Overall, we\u2019re pretty enthusiastic about the result. That\u2019s why we\u2019re happy to answer your requests to share some of the ideas and optimizations behind this new feature. For starters, we have a short video demonstrating the overall performance of the [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,5],"tags":[],"class_list":["post-498","post","type-post","status-publish","format-standard","hentry","category-crosscode","category-technical"],"_links":{"self":[{"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=\/wp\/v2\/posts\/498","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=498"}],"version-history":[{"count":16,"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=\/wp\/v2\/posts\/498\/revisions"}],"predecessor-version":[{"id":533,"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=\/wp\/v2\/posts\/498\/revisions\/533"}],"wp:attachment":[{"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=498"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.radicalfishgames.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}