4 ms·
Random Paths via Chiseling
- preinheimer 8y agoThis looks really cool! Any chance of showing an animated progression so we can see what each of the steps looks like?
- gamegoblin 8y agoCould you get similar results with the following procedure: 1. Represent the world as a grid graph where each cell has a bidirectional edge to its orthogonal neighbors. 2. Randomly weight the edges. The distribution of these weights will affect the texture of the results and is a tunable parameter. 3. Compute a minimum spanning tree of the graph. 4. Fill in dead-ends ends of the minimum spanning tree unless the dead end contains a goal endpoint (in other words, prune branches of the minimum spanning tree that do not end in an endpoint).
- danielvf 8y agoWouldn't that result in a path quite weighted to the shortest real world actual distance?
- gamegoblin 8y agoIt is not immediately obvious to me that that would be the case, since the MST is computed without regard to the actual goal endpoints.
- danielvf 8y agoAh, I'd missed that bit.
- eximius 8y agoWould Union-Find-Delete not be better than DFS? You remove a candidate point and if the all of the vertices you care about are not members of the same set you don't do that? (Assuming a copy of the UFD structure is faster than the DFS.)
- DannyBee 8y agoIf these are directed graphs, then the problem/algorithm described is equivalent (unless i'm misunderstanding this explanation) to incremental 2-edge-connectivity and various queries about it. The best known algorithms are O(mn), and they are very experimental. See, e.g., various papers you'll find here: https://dblp.uni-trier.de/pers/hd/g/Georgiadis:Loukas https://dblp.uni-trier.de/pers/hd/g/Georgiadis:Loukas For undirected graphs, this is also very well studied problem , and much easier (O(m+n)).