ID:1799492
 
Compartment Finding Algorithm

~ Note, colours just there to help visualize what this does. Colours not included.


1st: Why am I documenting this?

Mainly because I feel bloody amazing after writing it. Secondly, someone might actually use this (it is ready to go). Also it's the only open source one of it's kind that I know of on the forums.

2nd: What the frick is it?

This is a snipit of code you could use to group each little pocket of air or open 'compartment' available on your map. Thus allowing you to control how gas moves around.

Put simply a Compartment is list of turfs, compartments are identified when you start your game, compartments merge() allowing the exchange of gasses and compartments disappear if you blow up all the turfs they have.

3rd: How do I use this?

It's all automatic, simply use turf.getCOMP() to get it's compartment. Each turf has a COMPTagNo (compartment tag number) which tells you what compartment it's on as well. If two turfs have the same COMPTagNo then they are part of the same compartment and therefore connected on the map by open air.

The only thing you HAVE to do is when you've done some amount of deleting turfs you MUST call buildCompartments(). I advise calling this after you've done all the deleting you want to do. It would be a waste calling this several times in the same millisecond.

4th: Where do I go for help with this?

You can contact me on the pager or post below but if you're trying to understand what a line of code does then you could also try the Developer Help section.

/* Compartment Definition

These objects (represented as any number of turf objects)
are here to hold varying amounts of gas.

Compartments are created upon the creation of turfs,
they don't exist without turfs and their creation is
automatic.

*/


var/nextCOMPTag = 0 // Always unique

Compartment
var
list/contents = list()
tagNo = null // The number component only of the tag

New()
tag = "COMP:[nextCOMPTag]" // COMP:15 example. Uniquely identifies this compartment
tagNo = nextCOMPTag
nextCOMPTag ++

proc
add(turf/someTurf)
contents += someTurf

remove(turf/someTurf)
contents -= someTurf

merge(Compartment/someCOMP) // This happens automatically when more than one compartment collide
for(var/turf/someTurf in someCOMP.contents)
contents += someTurf
someTurf.COMPTagNo = tagNo
del someCOMP

/* Atom Expansion For Compartments

Any atom can now be capable of blocking gas,
e.g windows, doors and walls.

By default everything blocks gas unless
otherwise said.

*/


atom
var
blocksGas = 1

/* Turf Expansion For Compartments

Each turf that can hold gas must have a compartment.
A turf's compartment is decided upon its creation.

*/


turf
var
COMPTagNo = null

New()
if(type == /turf) return
if(!worldLoading) floodFillCOMP()
..()

Del()
var/Compartment/currCOMP = locate("COMP:[COMPTagNo]")
if(currCOMP)
for(var/turf/T in currCOMP.contents)
T.COMPTagNo = null
del currCOMP
..()

proc
getCOMP()
return locate("COMP:[COMPTagNo]")

doesBlockGas()
if(blocksGas) return 1
for(var/atom/thing in contents)
if(thing.blocksGas) return 1

assignCOMP()
if(COMPTagNo != null) return 0
var/Compartment/newCOMP = new/Compartment()
COMPTagNo = newCOMP.tagNo
newCOMP.add(src)
return 1

switchCOMP(tagNo)
COMPTagNo = tagNo
if(COMPTagNo)
var/Compartment/oldCOMP = locate("COMP:[COMPTagNo]")
oldCOMP.remove(src)

var/Compartment/chosenCOMP = locate("COMP:[tagNo]")
chosenCOMP.add(src)

floodFillCOMP() // Automatically flood outwards building its compartment.

// Setup
if(!assignCOMP()) return
var/Queue/todoQueue = new/Queue()
todoQueue.enqueue(src)

// Begin flooding outward to get every turf in compartment
while(!todoQueue.isEmpty())

var/turf/currTurf = todoQueue.dequeue()
currTurf.switchCOMP(COMPTagNo)

var
turf/north = get_step(currTurf,NORTH)
turf/south = get_step(currTurf,SOUTH)
turf/east = get_step(currTurf,EAST)
turf/west = get_step(currTurf,WEST)

if(north && !todoQueue.contents.Find(north) && !north.doesBlockGas() && north.COMPTagNo == null) todoQueue.enqueue(north)
if(south && !todoQueue.contents.Find(south) && !south.doesBlockGas() && south.COMPTagNo == null) todoQueue.enqueue(south)
if(east && !todoQueue.contents.Find(east) && !east.doesBlockGas() && east.COMPTagNo == null) todoQueue.enqueue(east)
if(west && !todoQueue.contents.Find(west) && !west.doesBlockGas() && west.COMPTagNo == null) todoQueue.enqueue(west)

/* Handle any merging that needs to be done */

var/list/COMPsToMerge = list()
if(north.COMPTagNo != COMPTagNo && !COMPsToMerge.Find(north.COMPTagNo)) COMPsToMerge += locate("COMP:[north.COMPTagNo]")
if(south.COMPTagNo != COMPTagNo && !COMPsToMerge.Find(south.COMPTagNo)) COMPsToMerge += locate("COMP:[south.COMPTagNo]")
if(east.COMPTagNo != COMPTagNo && !COMPsToMerge.Find(east.COMPTagNo)) COMPsToMerge += locate("COMP:[east.COMPTagNo]")
if(west.COMPTagNo != COMPTagNo && !COMPsToMerge.Find(west.COMPTagNo)) COMPsToMerge += locate("COMP:[west.COMPTagNo]")
COMPsToMerge += locate("COMP:[COMPTagNo]")

if(COMPsToMerge.len >= 2)

var/Compartment/largestCOMP = COMPsToMerge[1]
for(var/Compartment/C in COMPsToMerge)
if(C.contents.len > largestCOMP)
largestCOMP = C

COMPsToMerge -= largestCOMP

for(var/Compartment/C in COMPsToMerge)
largestCOMP.merge(C)

/* World Expansion For Compartments */

var
worldLoading = 1

world
New()
..()
worldLoading = 0
buildCompartments()

proc
buildCompartments()

// Find open turf
var/list/openTurf = list()

for(var/turf/someTurf in world)
if(!someTurf.doesBlockGas() && someTurf.COMPTagNo == null)
openTurf += someTurf

// Flood fill these where possible until none are left.
while(openTurf.len)
var/turf/next = openTurf[1]
next.floodFillCOMP()

for(var/turf/someTurf in openTurf)
if(someTurf.COMPTagNo != null)
openTurf -= someTurf

// All turf that can have a compartment now have one
For those astute people who are interested in the finer details.

I'm using a variation on an iterative 4 directional flood fill: http://en.wikipedia.org/wiki/Flood_fill

Followed by merging largest compartment by smaller compartments if other compartments are found.
cool