Create accountLogin

Recent searches

No recent searches

Search options

Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!

Administered by:

Server stats:

2.8K
active users

mathstodon.xyz: AboutStatusProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.3.7

#ShortestPathAlgorithm

0 posts0 participants0 posts today
Zeno Rogue<p>In Astarguesser, you are given a map with obstacles, and your task is to guess how good the A* algorithm will be at finding the shortest path from the entrance to the exit.</p><p>What is A*?</p><p>Let us start with Breadth First Search (BFS). In this algorithm, we proceed in waves: find all locations next to the source, then next to these locations, etc., until we reach the target. It is obvious that we will find the shortest path to the target this way, and also easy to implement on the computer: all the locations we reach are simply put in a queue, the location we explore next is always the one which was reached the earliest.</p><p>In A*, instead, we instead try to more promising directions first. While in BFS, the order is generally based on (the number of steps), in A* it is (the number of steps so far + heuristics), where &#39;heuristics&#39; is some approximation of the the number of steps we still need to take (for example, the number of steps to the exit, not taking obstacles into account). If the heuristics is &#39;admissible&#39; (not greater than the actual length of path to the exit) it is also guaranteed to find the shortest path. (See Red Blob Games for more details.)</p><p>A* seems to be the goto algorithm used by game developers for pathfinding purposes. But it rarely seems that good (even if the heuristics and tiebreakers are chosen reasonably). Maybe BFS (with its simplicity and good performance tue to the avoidance of priority queues), or some algorithm that takes into account the fact that you are usually pathfinding many times, could be more appropriate for your game?</p><p>PLAY ONLINE ON ITCH.IO: <a href="https://zenorogue.itch.io/astarguesser" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">zenorogue.itch.io/astarguesser</span><span class="invisible"></span></a></p><p><a href="https://mathstodon.xyz/tags/ShortestPathAlgorithm" class="mention hashtag" rel="tag">#<span>ShortestPathAlgorithm</span></a> <a href="https://mathstodon.xyz/tags/pathfinding" class="mention hashtag" rel="tag">#<span>pathfinding</span></a> <a href="https://mathstodon.xyz/tags/educationalgame" class="mention hashtag" rel="tag">#<span>educationalgame</span></a> <a href="https://mathstodon.xyz/tags/procgen" class="mention hashtag" rel="tag">#<span>procgen</span></a> <a href="https://mathstodon.xyz/tags/gamedev" class="mention hashtag" rel="tag">#<span>gamedev</span></a></p>
Pustam | पुस्तम | পুস্তম🇳🇵<p>From GPS navigation to network-layer link-state routing, Dijkstra’s Algorithm powers some of the most taken-for-granted modern services.</p><p>&quot;Dijkstra’s Shortest Path Algorithm in Python&quot; by Micah Shute 👉 🔗 <a href="https://www.cantorsparadise.com/dijkstras-shortest-path-algorithm-in-python-d955744c7064" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://www.</span><span class="ellipsis">cantorsparadise.com/dijkstras-</span><span class="invisible">shortest-path-algorithm-in-python-d955744c7064</span></a></p><p><a href="https://mathstodon.xyz/tags/ShortestPath" class="mention hashtag" rel="tag">#<span>ShortestPath</span></a> <a href="https://mathstodon.xyz/tags/Algorithm" class="mention hashtag" rel="tag">#<span>Algorithm</span></a> <a href="https://mathstodon.xyz/tags/ShortestPathAlgorithm" class="mention hashtag" rel="tag">#<span>ShortestPathAlgorithm</span></a> <a href="https://mathstodon.xyz/tags/Python" class="mention hashtag" rel="tag">#<span>Python</span></a> <a href="https://mathstodon.xyz/tags/Dijkstra" class="mention hashtag" rel="tag">#<span>Dijkstra</span></a> <a href="https://mathstodon.xyz/tags/GPS" class="mention hashtag" rel="tag">#<span>GPS</span></a> <a href="https://mathstodon.xyz/tags/Network" class="mention hashtag" rel="tag">#<span>Network</span></a> <a href="https://mathstodon.xyz/tags/Navigation" class="mention hashtag" rel="tag">#<span>Navigation</span></a> <a href="https://mathstodon.xyz/tags/GPSNavigation" class="mention hashtag" rel="tag">#<span>GPSNavigation</span></a> <a href="https://mathstodon.xyz/tags/CantorsParadise" class="mention hashtag" rel="tag">#<span>CantorsParadise</span></a></p>
SearchLive feeds
About