For the examples here I kept room the room spiting to small sizes.In game it would be better to make them large and greedy. I'm still unsure about a reasonable slicing scheme but in generally the rooms should be reasonably large and they should also try to be as wide open as possible (vector pathing is your friend if you can do it). A set of rules can translate into code which would translate into a map.The advantage of a room method would be that you can keep subdividing the map into a simpler map . The room method also allows for arbitrarily large worlds without major loss of FPS due to long paths. The main disadvantage is the amount of coding and design it would take to create it.
In most of the examples here I'd group it all into 1 or 2 nodes . The grouping system simplify long range travel. Short range traveling is generally too simple to even consider. Even with the A* worst case example you don't really need a lot of rooms - you just need to turn it from a west ->east problem to a south-> east->north problem . As I said room system is a very complicated solution but it has major advantages.
A path caching to way-points scheme is very easy to add. Toady can give the user a set of 20 waypoints and he'll save caches of all the paths between them . This way first thing anyone pathing would do is call the heuristic about 1+2*20 times. once for source destination and then 20 src<->waypoint and 20 dst<->waypoint. With smart placement the players can simplify very long distances into a very simple highway. With this system you got 1 major advantage - no complicated placement scheme and very a deterministic code . The players would plant the waypoints and they would generate a huge FPS gain .
edit : minor changes to my simple
test program (too lazy to rewrite it)
- added ability to add waypoints
- added ability to set start point
- added ability to set destination point
- the bfs now search from start point if it's valid
edit2: another major update to my test program - started using some simple CSS
- squared the maze
- added
A star NAVIGATION I got from 46 dogs's blog( I got reference to it on the page)
- added path highlighting
edit3:
- Path caching done using user set waypoints (display processing time for generation)
- Find path renamed to Find Path A*
-
"Find Path using waypoints" was Added. This uses the path cache to generate path from source to destination it's about a factor of 10 faster than a* with good placement. there is no path smoothing yet. it uses the method I described above to find 2 intermediate to the cached path.
- removed the bfs maze to prevent confusion
have fun
edit4: future plans:
-expand the maze... done~
-add a better save/load function ...in progress
-add path cache size and optimized cache size(it currently saves 4byte per steps and I want to change it to 4bits per step or less)
-path smoothing to prevent zigzag into the waypoint (haven't looked into how it's done but shouldn't be tough)
-when the maze is bigger we'll talk about optimizations , automatic placement etc
small mazes have their limitations....
- the room splitting pathing algorithm is up next ...
edit5:
- expanded the grid to 32X32 nodes (framed in 34X34 box)
- modified save/load function to support loading old format and save/load new v01 format :v01RRCCM* R=rows C=columns M= HEX representation binary maze data.
- fixed some waypoint deleting bugs not updating cache correctly - there is still a bug when 1 waypoint is closest to both source and destination
- forum output now shows the contents of the maze which include waypoints an start/destination
-changed waypoint symbol from '$' to 'w'.
more future stuff I'll add:
-load parameter shrinking(it's huge now) - run length encoding, LZW or switch to b64(256-> 170 byte)
-load maze from edit box (quick pasting to forum)
-maze size scaling (or something) and maze forum output scaling
-maybe better maze visuals .
-clickable "paint tools"