Auto-generating maps

For developmental things relating to the graphics of the game.
User avatar
TiTnAsS
Match Winner
Posts: 655
Joined: Sun Jan 23, 2005 2:44 am
Location: Reppin the Bay Area!

Post by TiTnAsS »

...there wouldnt be any looking and trying to find your way out though, there would only be race to the end using the minimap!
Damn, it sure has been a while!
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

It's not that easy at high speeds. At 3 cells/sec there is just no time to look for a way out on the map. With a little practice looking ONLY on the map may help though.
ˌɑrməˈɡɛˌtrɑn
User avatar
Lucifer
Project Developer
Posts: 8640
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

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!
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?

Looking at a map != reading a map
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
User avatar
TiTnAsS
Match Winner
Posts: 655
Joined: Sun Jan 23, 2005 2:44 am
Location: Reppin the Bay Area!

Post by TiTnAsS »

meh i think itd be alot easier but w/e
Damn, it sure has been a while!
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

I started working on code that solves mazes. Obviously it won't be able to generate maze maps, but I hope it's going to be fun anyway. :)
User avatar
Tank Program
Forum & Project Admin, PhD
Posts: 6711
Joined: Thu Dec 18, 2003 7:03 pm

Post by Tank Program »

There's this xscreensaver that creates mazes and then solves them...
Image
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

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.
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

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?
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

Sounds like a*, only without the early pruning of paths that can't be the shortest one anyway. So yes, sounds good. Is the stored information per node by chance
- the link the cheapest path from the start point enters it from
- the cost of the shortest path
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

Yep, and I guess you guessed how it works?
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

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.
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

Not exactly what I did. It will find a the cheapest path for ALL reachable nodes. The result could be like the PNG I attached.
Attachments
mazesolver.png
mazesolver.png (4.07 KiB) Viewed 10027 times
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

If that's your goal, of course, you can get by without that A* complexity. Optimizing for quickly finding the shortest path to the destination does not pay off if you want all paths anyway ;)
User avatar
Jonathan
A Brave Victim
Posts: 3391
Joined: Thu Feb 03, 2005 12:50 am
Location: Not really lurking anymore

Post by Jonathan »

Now can you describe exactly how it works? :) At this time only one backtrack is possible per node.
User avatar
Z-Man
God & Project Admin
Posts: 11585
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

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.
Post Reply