Page 1 of 1
Drawing lines between random points
Posted: Thu Feb 14, 2013 5:28 pm
by Psymong
Hello all!
I'm trying to generate a random map of points with multiple routes through them.
However, the method i've come up with isnt very efficient;
sometimes in generates some very cluttered areas, and sometimes clusters of points are cut off from the rest.
can someone please advise a better way of doing this.
I'm quite new to all this, so please excuse my terrible code.
Thanks!
EDIT:
I should probably be more specific;
I need a system that will draw lines connecting these points, that will allow for multiple routes and ensure that all the points on the map are accessible.
but will also connect them in a neat and logical way.
i cant seem to figure one out because my brain is neither neat nor logical.
thanks again
Re: Drawing lines between random points
Posted: Thu Feb 14, 2013 8:18 pm
by micha
If I get your question correct, you want to find a method to generate a map, that has a nice shape, in the sense that it is not cluttered, and all nodes are somehow connected.
I don't have any experience in that field, but I can name the two disciplines, you are looking for: graph theory and procedural generation. This will serve you as a starting point to google things.
Graph theory is the mathematical theory of graphs, which are a set of nodes and edges (what you consider a "map")
Procedural generation deal with generating game contend based on "smart" random algorithms.
Edit:
Two suggestions:
1) You can check, if all nodes are connected with the flood-fill algorithm.
2) Maybe you get nice results already if you add edges as follows: Start with nodes only, no edges. Then add an edge between the two nodes, that are closest to each other. Repeat this step, but only add edges, such that no two edges cross.
Re: Drawing lines between random points
Posted: Thu Feb 14, 2013 8:27 pm
by Psymong
That's kind of it.
I've managed to get a system for generating points (with a bit of help) that works quite well.
The problem at the moment is working out a way to draw lines between these points that ensures they all connect (but not necessarily directly connect).
thanks for the pointer though, i already have been reading up on procedural generation stuff (most of it is a bit out of my league maths-wise). This particular problem is just a bit of lua logic i cant get my head around
EDIT:
I dont understand what you mean by either of those points, but i'll get googling!
cheers
Re: Drawing lines between random points
Posted: Sat Feb 16, 2013 2:55 am
by Psymong
Ok, with the help of a very kind person on #love, i've come up with a better system for connecting the points.
however, it is still possible for clusters of points to be disconnected.
i.e. there are parts of the map that can be inaccessible to the player.
how can i check for this and ensure it doesnt happen.
any help would be GREATLY appreciated.
this is starting to hurt my brain.
thanks!
Re: Drawing lines between random points
Posted: Sat Feb 16, 2013 4:17 am
by substitute541
Psymong wrote:Ok, with the help of a very kind person on #love, i've come up with a better system for connecting the points.
however, it is still possible for clusters of points to be disconnected.
i.e. there are parts of the map that can be inaccessible to the player.
how can i check for this and ensure it doesnt happen.
any help would be GREATLY appreciated.
this is starting to hurt my brain.
thanks!
Simple. Just check all of the nodes if one is empty. If so, connect it to a random node, or what your algorithm says.
Re: Drawing lines between random points
Posted: Sat Feb 16, 2013 10:58 am
by micha
substitute541 wrote:Simple. Just check all of the nodes if one is empty. If so, connect it to a random node, or what your algorithm says.
This is not enough. If you have four nodes, A,B,C,D and the connections A-B and C-D, each node has a connection, but the graph is separated.
You can check for connectivity with a sort of flood-fill-algorithm:
Start with a graph and mark all nodes as "not-done" and "not-connected". Then mark one node as "connected".
Now repeat the following:
Find a node X that is "not-done" but "connected". If you find one, then mark all of the neighbors of X as "connected" and mark X as "done".
The loop terminates if you don't find any node that is "not-done" but "connected".
If then there are any nodes left, that are marked as "not-connected", then the graph is not connected and you have at least one separate node or cluster.
Re: Drawing lines between random points
Posted: Sat Feb 16, 2013 11:37 am
by Psymong
Thankyou micha, now i understand what you mean by using flood-fill in this context.
I still cant quite work out how to incorporate this into my code though;
so i should put the results of these checks in a separate table, adding the values 'connected' to all each of the points in its pointer[x].linkedto value, and then adding a value 'done' into that table, right?
how do i then work out where to make the new connections?
Apologies if i'm not making much sense, im still quite new to all this and getting increasingly confused as i go on
cheers!
Re: Drawing lines between random points
Posted: Sat Feb 16, 2013 12:46 pm
by micha
Psymong wrote:I still cant quite work out how to incorporate this into my code though;
so i should put the results of these checks in a separate table, adding the values 'connected' to all each of the points in its pointer[x].linkedto value, and then adding a value 'done' into that table, right?
That is correct. You probably have a table, containing all the nodes. There you can either add a field containing the checks like this:
Code: Select all
node[i].done = false
node[i].connected = false
or you create a separate table only for the checks:
Code: Select all
done[i] = false
connected[i] = false
In both cases, the index i should be the same as the corresponding node.
Psymong wrote:how do i then work out where to make the new connections?
After applying the algorithm you have divided the nodes into two groupds: connected and not-connected. Pick one in each group and add an edge. Then run the flood-fill-algorithm again, to check if you need more edges, or you are done.