Defining the land masses.

Page: 1 2
ID:272426
 
Jul 7 2008, 4:54 pm (Edited on Jul 8 2008, 5:18 am)
Take notice at the below screenshot. I made a land generator and I'm wondering how I can define the large/medium land masses as "Continent1","Continent2","Continent3" and so on and the tinier land masses as "Island1","Island2","Island3" etc.
Note: Islands will be bigger than this, because it will have different size maps. I need to know how to calculate the "large/medium" and "small" and define them as separate masses of land.

Image Hosted by ImageShack.us
Jul 7 2008, 5:04 pm (Edited on Jul 7 2008, 5:43 pm)
Datums, as usual, will come in handy here.
#define ISLAND    1
#define CONTINENT 2

turf
    var/land_mass/land_mass

    water
    land

land_mass
    var
        list
            land = list(/turf/land)
            components[0]

        bound_size = 50 //This is how many turfs have to be
                        //have to be in the components list
                        //to be considered a continent.
        land_type = ISLAND

    New(turf/start, b = null, list/l = null)
        if(!isnull(b)) bound_size = b
        if(!isnull(l)) land = l

        spawn() GetComponents(start)

    proc
        GetComponents(turf/t)
            //This implements a breadth-first search (I
            //think. I don't know much about graph theory).

            var/list/v = oview(t, 1) //Get all the turfs
                                     //in view of t, sans
                                     //t itself.
            for(var/turf/t in v)
                if((t.type in land) && !(t in components))
                    //If t is a land type, and t isn't
                    //already in the list, add it, and
                    //search the turfs around it.
                    Add(v)
                    .(v) //Shorthand to call recursion.

            CheckType()

        Add(turf/t)
            components += t
            t.land_mass = src
        Remove(turf/t)
            components -= t
            t.land_mass = null

        CheckType()
            land_type = components.len > bound_size ? CONTINENT : ISLAND
            return land_type
Jul 7 2008, 5:08 pm
In response to Popisfizzy
alright, also. At what point would i go about creating a new datum?
Jul 7 2008, 5:20 pm
In response to Chibi-Gohan0
Oh, whoops, I forgot to handle that. In that case, alter /land_mass.New() to this:
    New(turf/start, b = null, list/l = null)
        if(!isnull(b)) bound_size = b
        if(!isnull(l)) land = l

        Add(start)
        GetComponents(start)

Then do this:
proc/get_land_masses()
    for(var/turf/land/t in world) //Or whatever qualifies
                                  //as land.
        if(!t.land_mass)
            new/land_mass(t)

Depending on the size of the generated map, this could get processor intensive (I don't know how to write other searching algorithms, so there may be better ways). I'd throw a sleep(-1) in the for loop, or possible the recursive loop. There's a small chance that you could end up with a large land mass, which would make the recursive loop intensive.
Jul 7 2008, 5:25 pm
In response to Popisfizzy
Sounds great, I'll test later for the intensive loops, but i believe you also forgot one thing. How would I name each mass (name generator or whatever) "Continent1" etc.
Ie it finds a continent and name it "United States of Frankford". (I'm not asking for a name generator, but instead a way to name it, and even search for it.)

...Or can i just use the name variable for that?
Jul 7 2008, 5:35 pm
In response to Chibi-Gohan0
 
land_mass
    var/name

    proc/SetName(n)
        name = n
        tag = ckey(n)

The tag is set up so you can just use locate() to find the land_mass object.
Jul 7 2008, 5:41 pm
In response to Popisfizzy
Okay, so while its all good and dandy at compile time. I tried it out at runtime and i get this error:

proc name: CheckType (/land_mass/proc/CheckType)
runtime error: Cannot write to list.land_mass.
proc name: Add (/land_mass/proc/Add)
runtime error: type mismatch: cannot compare /list (/list) to 50

and i get it repeatedly.
Jul 7 2008, 5:45 pm
In response to Chibi-Gohan0
Er, whoops. The line in /land_mass.CheckType() should be components.len > [...]
Jul 7 2008, 5:49 pm (Edited on Jul 7 2008, 6:02 pm)
In response to Popisfizzy
Still get a similar error.
runtime error: Cannot write to list.land_mass.
proc name: Add (/land_mass/proc/Add)
usr: Chibi-Gohan0 (/mob/Player)
src: /land_mass (/land_mass)
call stack:
/land_mass (/land_mass): Add(/list (/list))
/land_mass (/land_mass): GetComponents(Land (11,1,1) (/turf/Land))
/land_mass (/land_mass): New(Land (11,1,1) (/turf/Land), null, null)
get land masses()
Chibi-Gohan0 (/mob/Player): Generator()
Jul 7 2008, 5:55 pm
In response to Chibi-Gohan0
There's no error listen, so I can't help you. You probably copy/pasted wrong.
Jul 7 2008, 5:56 pm
In response to Popisfizzy
Popisfizzy wrote:
There's no error listen, so I can't help you. You probably copy/pasted wrong.
Alright, Thanks for the help.
Jul 7 2008, 8:59 pm (Edited on Jul 7 2008, 9:09 pm)
I'll take a more first-principles look at it than Pop here.

Basically, you're trying to find continents on your map. This is the same as a computer-science problem called 'connected components' - you can imagine your map is a graph, where each turf has a 'link' to every other turf you can move to from there - but, importantly, there is no link between a turf and water, because you can't move into water.

So you're trying to find out how many sub-maps there are, and how big they are.

A simple solution:

- Put all the land turfs on your graph in a list.
- Step through each turf, find all the turfs reachable from it, and add them to the landmass, then remove them from the list of all turfs - that is one continent
- repeat until there are no more turfs left.

Labelling something as an 'island' or 'continent' is just a matter of how many turfs there are.

Note that this is basically Pop's approach.

landmass
    var/list/turfs=list()

    proc/addTurfs(list/l)
        for(var/k in l) turfs.Add(k)

turf
    proc
        getReachable()
            if(density) return list(src)
            var/list/ret = list(src)

            for(var/i=1, i<=ret.len, i++)
                var/turf/t = ret[i]
                for(var/turf/t2 in orange(1, t))
                    if(!(t2.density||(t2 in ret))) ret+=t2
            return ret
        
proc
    findLandmasses()
        var/list/landlist=list()
        var/list/landmasses=list()
        
        for(var/turf/land/l) landlist+=l

        while(landlist.len>0)
            var/landmass/l = new()
            var/turf/t = landlist[1]
            var/list/ts = t.getReachable()
            landlist-=ts
            l.addTurfs(ts)
            landmasses.Add(l)

        return landmasses
        
turf
    icon = 'test.dmi'
    land
        icon_state = "land"
    
    water
        density = 1
        icon_state = "water"
        
mob
    verb/test()
        var/list/l = findLandmasses()
        src << l.len


Uncommented and untested. It should at least compile. It assume your 'land' turf is called '/turf/land', and that water is dense and land is not - this may cause issues with, say, trees or mountains being considered ocean. You should consider implementing an 'isLand()' proc.

To name the landmasses this generates, you'll need to extend the landmasses datum.

Hopefully this is helpful. Good luck.

EDIT: Decided I should probably test it, realised that I'm a bit rusty when I ran headlong into, first, DM lists starting at 1, not 0, and second, not being able to change a list you're looping over. This is a fixed, semi-tested version that you can just drop into a new project and fiddle with the 'test' verb outputs the number of landmasses in the world.

Have fun fiddling.
Jul 7 2008, 11:36 pm
In response to Jp
Jp wrote:
'connected components' - you can imagine your map is a graph, where each turf has a 'link' to every other turf you can move to from there - but, importantly, there is no link between a turf and water, because you can't move into water.

Did you forget to fill in the link, or was it on purpose? Either way, the topic discussing this should be linked.
Jul 8 2008, 12:23 am
In response to Kaioken
Errr... actually, I tried to link to the Wikipedia article, and have no idea how that BYOND post is what came out.
Jul 8 2008, 12:59 am
In response to Jp
I suppose that'd be because you forgot (or otherwise on accident) to fill the href attribute, and since there is no "http://" in the beginning of the URL, it takes it in as a local path, and since there's nothing there it links to the same page. =P
Jul 8 2008, 1:08 am
In response to Jp
While that would do most of what i need, it still misses the point of figuring if its an island or a continent, then naming it, so that i can come back later and look it up under a certain name (it being one list of land mass all under the same name).
Jul 8 2008, 1:58 am
In response to Chibi-Gohan0
Those are extensions I left to you. :P.

A quick explanation of how I would go about that - with no code this time, just a description.

The 'landmass' datum needs a 'name' var, and the following procedures:

getName()
setName()
getSize()
isIsland()
isContinent()

That do basically what they say on the tin. Getting and setting a name is easy, the 'size' of a landmass can just be the length of its turf list - that's the area of it, basically. Whether it's an island or a continent is a fuzzy question - something for which fuzzy logic would be quite useful - but if you just need a crisp answer, saying that anything below a certain size is an island, everything above is a continent is the easy and obvious way to do it.

If you want to be able to get landmasses by name (e.g., continent["europe"]), you'll need to construct an associative list of continent name associated with the continent reference - that's easy enough to do.
Jul 8 2008, 4:42 am (Edited on Jul 8 2008, 4:52 am)
In response to Jp
hmm i'm not getting it fully. Lets say i have a bunch of land turfs, all of which are all processed though that system. How would i go about getting the datum's info by clicking that turf? When i try doing something similar i always get a turf for a result instead of a the landmass datum.

For example,
for(var/landmass)
    world<<landmass

This will allways give me a turf for the output, not the desired datum.

and it cant find the datum's name variable
Its a compile time error.
landmass
    var/name = "Continent1"
for(var/landmass in world)
    world<<landmass.name

This is just an example though.
Jul 8 2008, 5:02 am (Edited on Jul 8 2008, 5:09 am)
In response to Chibi-Gohan0
I added things for you.
landmass
    var/name
    var/list/turfs=list()

    proc/addTurfs(list/l)
        for(var/k in l)
            turfs.Add(k)
            if(istype(k,/turf/land)
                var/turf/land/j = k
                j.landmass = src

turf
    proc
        getReachable()
            if(density) return list(src)
            var/list/ret = list(src)

            for(var/i=1, i<=ret.len, i++)
                var/turf/t = ret[i]
                for(var/turf/t2 in orange(1, t))
                    if(!(t2.density||(t2 in ret))) ret+=t2
            return ret
        
proc
    findLandmasses()
        var/list/landlist=list()
        var/list/landmasses=list()
        
        for(var/turf/land/l) landlist+=l

        while(landlist.len>0)
            var/landmass/l = new()
            var/turf/t = landlist[1]
            var/list/ts = t.getReachable()
            landlist-=ts
            l.addTurfs(ts)
            landmasses.Add(l)

        return landmasses
        
turf
    icon = 'test.dmi'
    land
        icon_state = "land"
        var/landmass/landmass

        Click() //for testing purpose only
            usr << landmass ? landmass.name : "Unknown landmass"
    
    water
        density = 1
        icon_state = "water"
        
mob
    verb/test()
        var/list/l = findLandmasses()
        src << l.len
Jul 8 2008, 5:10 am
In response to Jemai1
That doesn't work.
    Click()
        usr << landmass ? landmass.name : "Unknown landmass"

Land.dm:23:? :warning: statement has no effect

Not to mention that in addturfs() you put turf.landmass instead of k.landmass
Page: 1 2