[Home] [Downloads] [Search] [Help/forum]

Gammon Forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  MUSHclient
. -> [Folder]  Plugins
. . -> [Subject]  (mapper drawing) force-directed layout for graphs with default layouts
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?

(mapper drawing) force-directed layout for graphs with default layouts

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Pages: 1 2  3  4  

Posted by Tsunami   USA  (204 posts)  [Biography] bio
Date Wed 12 May 2010 01:11 AM (UTC)
Message
Haven't posted here in a while but I lurk from time to time :) In my spare time currently I've written an implementation of a force-directed graph layout engine for graphs with well-defined node/node angles (i.e. MUD maps). For those interested I've basically taken the Fruchterman-Reingold algorithm, tweaked it a bit, and added the notion of edge torque.

It would be quite useful for visually displaying maps since it can untangle a lot of the messiness of not quite Euclidean geometry of many MUD layouts without user aid (though user aid can improve layouts as well).

It's currently in C#, because I like that for prototyping and I wanted to experiment with CLRv4 code contracts anyways (IMHO, not very easy to use, and of marginal benefit without an extraordinary amount of work).

So my question is what format would make this easiest to integrate with whatever mapping features exist today? I was thinking of rewriting in c++ and exposing it as a dll, but I'd have to look at how that integrates with lua (and then I'd be tempted to try to integrate the boost graph library instead of the one I rolled myself), so I'm open to suggestions.

Once/If I rewrite it I'll prolly stick it up on github or google code and start looking for large graphs to test it on, as so far I've only tested it on a couple simple layouts and edge cases (no more than 6 nodes).

I would also want to experiment with a single pass whole graph layout vs multi pass graph subset layout. Anyways, questions, comments, etc, all welcome :)
[Go to top] top

Posted by Nick Gammon   Australia  (21,322 posts)  [Biography] bio   Forum Administrator
Date Reply #1 on Thu 13 May 2010 05:49 AM (UTC)
Message
The current mapping is implemented in Lua using a plugin and a module called by the plugin. Something like a DLL could be one way of doing it.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by LupusFatalis   (154 posts)  [Biography] bio
Date Reply #2 on Fri 14 May 2010 05:51 AM (UTC)
Message
This sounds pretty sweet, I'd love to test it out when you get a working version.
[Go to top] top

Posted by Nick Gammon   Australia  (21,322 posts)  [Biography] bio   Forum Administrator
Date Reply #3 on Fri 14 May 2010 06:08 AM (UTC)
Message
Sound interesting, but I note from Wikipedia that "the typical force-directed algorithms are generally considered to have a running time equivalent to O(V^3), where V is the number of nodes of the input graph".

That is, the running time goes up as the cube of the number of rooms, so 6 rooms could be OK (ie. running time of 216 x O, whatever O is), but for say 40 rooms it would be 64,000 x O, so that could be difficult to run interactively. Could be OK if you built the map offline perhaps.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #4 on Fri 14 May 2010 07:16 AM (UTC)
Message
The notation O(V^3) means "on the order of V^3"; O isn't a value but just notation to give the order of the algorithm's run time.

To be a little more precise (while still waving hands somewhat) it means that A*V^3 + B is a bound for the function's run time, for constant values A and B.

In short, it means that the function will be very slow for large enough input sets. :P

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (21,322 posts)  [Biography] bio   Forum Administrator
Date Reply #5 on Fri 14 May 2010 08:08 AM (UTC)
Message
I thought it meant something like that. So if for instance, O is a millisecond, then 216 milliseconds would be OK, but 64 seconds might be a bit slow. ;)

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #6 on Fri 14 May 2010 08:29 AM (UTC)
Message
O isn't a variable, and it doesn't have a value. It's just a notation for algorithmic complexity. O(1) means constant time, O(x) means linear time. The O itself is just a marker, called Big-O Notation.

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

Posted by LupusFatalis   (154 posts)  [Biography] bio
Date Reply #7 on Fri 14 May 2010 03:43 PM (UTC)
Message
Ah thats pretty god awful didn't realize the algorithm was O(n^3).

For "completed maps" however, it might be nice to do. i.e. in a standalone app that just reads a database and cranks out a graphic of some kind?

Or, while running it constantly would be problematic in large databases, it might be a worthwhile investment for a post-script type process.
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #8 on Fri 14 May 2010 06:40 PM (UTC)
Message
In general the algorithm is bad, but you have constraints on the input that you can probably exploit. For example, it's extremely unlikely that nodes on the fringe of the graph will somehow link all the way back to the center. I can't articulate precisely how this will help, but basically you have a special case of the graph layout problem and surely this can be used to give serious hints to the mapper. For example, you know that the directions really should be to the north, south, east, west, etc., and this can be very useful: it knows that it needs to stretch exits rather than go nuts with arbitrary node positioning.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Tsunami   USA  (204 posts)  [Biography] bio
Date Reply #9 on Mon 17 May 2010 05:00 PM (UTC)

Amended on Tue 18 May 2010 12:57 AM (UTC) by Tsunami

Message
This algorithms doesn't have a great running time abstractly true, but as with all algorithms, there are lots of ways to make this workable.


  1. Only run the simulation on visible rooms - this cuts down on the number of rooms enormously. Even for 100 rooms or so, modern computing makes this trivial. This does mean however, that map layout could change as the view adjusts, and new edges and nodes come into play. Still, this is a problem at the moment, so at least we're not going backwards.

  2. Run the algorithm once to layout. This seems like a good idea, but there are a number of problems in practice. Mostly, I don't know how well it will handle large numbers of one way exits and unsolvable non-euclidean geometries.

  3. Force-directed layouts are somewhat unique in terms user experience in that they are also n-body simulations. This means they can be displayed in a meaningful manner to the user DURING the simulation. So we don't necessarily have to block drawing until the simulation completes, we can update the drawing as we go along without overly displeasing a user. This means updating, layout out, and drawing the graph continuously in parallel.


I think #3 might be the best overall solution, but for now I'm just going with #1 since I'm basically prototyping. I also wanted to add that the running time is usually dominated by the calculation of node/node repulsion, which references every other node in the graph. If this can be eliminated or optimized (via Barnes-Hut techniques) running time may drop dramatically. Especially since MUD maps are rarely pathalogically densely connected ;)

I'll post some preliminary results in a moment.
[Go to top] top

Posted by Tsunami   USA  (204 posts)  [Biography] bio
Date Reply #10 on Mon 17 May 2010 05:12 PM (UTC)

Amended on Tue 18 May 2010 12:58 AM (UTC) by Tsunami

Message
I've done some initial layouts on a map of Achaea Nick was kind enough to send me. For those familiar, this is within the city of Shallam, limited to 60 rooms.

Initial layout:
http://i.imgur.com/yk21M.png

Result layout:
http://i.imgur.com/dDgyJ.png

Green lines represent one way exits, which unfortunately, the algorithms doesn't handle well (at all) at the moment, which is why they seem to have some odd layouts. The characters associated with each edge are for debugging to tell me what the desired orientation for that edge is (n, ne, e, etc...).

The most dramatic improvement is clear in the expansion of the left side of the map I think. Because I haven't gotten around to implementing some outside energy sink, larger simulations have a tendency to run forever if you let them at the moment. This means I can't give you a great idea of the speed of the algorithm, other than to say the initial layout happens extremely fast, and its basically oscillations from there on out :)
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #11 on Mon 17 May 2010 08:01 PM (UTC)
Message
Quote:
Even for 100 rooms or so, modern computing makes this trivial.

100^3 = 100*100*100 = 1,000,000

Maybe I'm being picky, but this isn't really "trivial". What makes this problem tractable is the set of assumptions that constrain the problem. As you said, MUD maps aren't pathological and the algorithm doesn't need to handle those cases well.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (21,322 posts)  [Biography] bio   Forum Administrator
Date Reply #12 on Mon 17 May 2010 09:14 PM (UTC)
Message
Tsunami said:

Dammit, Nick, your forum won't let me edit my posts :P
...
Also, if there is a way to turn the links above into true links, please feel free to edit those for me Nick. Thanks!


If you log in you should be able to edit your posts. I do it all the time. You can't edit without logging in.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Tsunami   USA  (204 posts)  [Biography] bio
Date Reply #13 on Mon 17 May 2010 09:47 PM (UTC)
Message
Even older computers these days should not have a problem handling a mere million floating point operations. See how long it takes your comp to run 2 or 3 million trigonometric functions. Further, big O notation should be used as an estimate of an algorithms growth rate and efficiency, not running time.

O(.000000000000000001 * N^3 + 100000000000) is still O(N^3) despite the fact that for non-large N's it is dominated by a linear term.
[Go to top] top

Posted by Nick Gammon   Australia  (21,322 posts)  [Biography] bio   Forum Administrator
Date Reply #14 on Mon 17 May 2010 10:08 PM (UTC)
Message
Try enabling cookies on your profile.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


35,347 views.

This is page 1, subject is 4 pages long: 1 2  3  4  [Next page]

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at FutureQuest]