Auto-generating maps
- Lucifer
- Project Developer
- Posts: 8640
- Joined: Sun Aug 15, 2004 3:32 pm
- Location: Republic of Texas
- Contact:
At swampland or breakfast speeds, you may not even have time to read your map. Did you happen to notice how many dead ends were in the map Jonathan showed?TiTnAsS wrote:...there wouldnt be any looking and trying to find your way out though, there would only be race to the end using the minimap!
Looking at a map != reading a map
- Tank Program
- Forum & Project Admin, PhD
- Posts: 6711
- Joined: Thu Dec 18, 2003 7:03 pm
- Jonathan
- A Brave Victim
- Posts: 3391
- Joined: Thu Feb 03, 2005 12:50 am
- Location: Not really lurking anymore
There's also a Mac screensaver, but unfortunately it screws up badly on 10.4 (and the other way around).
Edit: No problem when building from source.
Edit 2: Replace that with "less often, but still fatal".
But I'm almost sure those solvers don't use the techniques I'm thinking about.
Edit: No problem when building from source.
Edit 2: Replace that with "less often, but still fatal".
But I'm almost sure those solvers don't use the techniques I'm thinking about.
- Jonathan
- A Brave Victim
- Posts: 3391
- Joined: Thu Feb 03, 2005 12:50 am
- Location: Not really lurking anymore
I hope I got my solver working. At least it survived a simple test case.
- Can solve any maze, not only perfect and block-based mazes.
- Bidirectional links don't exist. There are only unidirectional links.
- Give it a start node, and it'll start exploring the maze. When it's done, all reachable nodes are filled with all information needed to find the lowest-cost path from the start node, and the total cost of that path. If the path goes nowhere and cost is infinite, there is no solution.
Sounds good?
- Can solve any maze, not only perfect and block-based mazes.
- Bidirectional links don't exist. There are only unidirectional links.
- Give it a start node, and it'll start exploring the maze. When it's done, all reachable nodes are filled with all information needed to find the lowest-cost path from the start node, and the total cost of that path. If the path goes nowhere and cost is infinite, there is no solution.
Sounds good?
I guess
It must be something on the line of "Find the cheapest way from the start to a node by finding the cheapest ways to all neighboring nodes (connected by a link from the neighbor to the current node), and then choosing the node as origin where the cost of the path plus the cost of the link is lowest".
There are different orders in which you can do this; you can keep a list of currently possible path extensions (each list item stores a link from a node you already know the best path to to an unvisited node and the cost of the total path) where you always choose the list item with the least total costs, enter the path continuation data (source node/link and cost) into the link's target node and add all links going from the target node to not-yet-visited nodes to the list. And remove the other links going to that node.
In A* (IIRC, by algorithm zoology is a bit rusty), you don't choose the total costs up to now as a criterion for the link you add next; you choose the minimal expected total cost of the completed path. This assumes you have a lower bound for the cost of the minimal path of any node to the endpoint, something you don't have in general graphs. But you can take "length of path up to now plus Euclidian distance of the endpoint to the target node" if your graph represents paths in space and length is your only cost. This will find the best path directly if there are no obstacles.
It must be something on the line of "Find the cheapest way from the start to a node by finding the cheapest ways to all neighboring nodes (connected by a link from the neighbor to the current node), and then choosing the node as origin where the cost of the path plus the cost of the link is lowest".
There are different orders in which you can do this; you can keep a list of currently possible path extensions (each list item stores a link from a node you already know the best path to to an unvisited node and the cost of the total path) where you always choose the list item with the least total costs, enter the path continuation data (source node/link and cost) into the link's target node and add all links going from the target node to not-yet-visited nodes to the list. And remove the other links going to that node.
In A* (IIRC, by algorithm zoology is a bit rusty), you don't choose the total costs up to now as a criterion for the link you add next; you choose the minimal expected total cost of the completed path. This assumes you have a lower bound for the cost of the minimal path of any node to the endpoint, something you don't have in general graphs. But you can take "length of path up to now plus Euclidian distance of the endpoint to the target node" if your graph represents paths in space and length is your only cost. This will find the best path directly if there are no obstacles.
No. As I said, there are many different ways to order the processing.
However, I'd guess you're using A* without the H part of the metric and without the stop condition when hitting the target.
However, I'd guess you're using A* without the H part of the metric and without the stop condition when hitting the target.