Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to "verify" your details, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Entire forum ➜ MUSHclient ➜ Plugins ➜ (mapper drawing) force-directed layout for graphs with default layouts

(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 page

Pages: 1 2 3 4

Posted by

Tsunami USA (204 posts) 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 :)

Posted by

Nick Gammon Australia (23,046 posts) 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

Posted by

LupusFatalis (154 posts) 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.

Posted by

Nick Gammon Australia (23,046 posts) 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

Posted by

David Haley USA (3,881 posts) 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

Posted by

Nick Gammon Australia (23,046 posts) 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

Posted by

Twisol USA (2,257 posts) 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

Posted by

LupusFatalis (154 posts) 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.

Posted by

David Haley USA (3,881 posts) 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

Posted by

Tsunami USA (204 posts) 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.

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

Posted by

Tsunami USA (204 posts) 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 :)

Posted by

David Haley USA (3,881 posts) 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

Posted by

Nick Gammon Australia (23,046 posts) 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

Posted by

Tsunami USA (204 posts) 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.

Posted by

Nick Gammon Australia (23,046 posts) 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

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.

127,918 views.

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

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

Go to topic: Search the forum

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.