next »

[mesotes]

Hi everyone.. again.

So some of you may know Im working on a "simple paint program" which actually is quite right but not the whole truth. In the end, I want to do a Dwarf Fortress fortress designer. I know there is already one (or two?) out there which I dont really like to use , so I want to make my own and use it in Quickfort.

So far the plan was "pixeling" the fortress, each color standing for a specific keystroke.
Soon I realized you'll get overwhelmed by many different colors if I want to support every feature Quickfort has to offer.
Therefore I decided to use tiles instead.

For all who dont know dwarf fortress here is a little illustration:

(in the editor, as well as in the game you see one layer
at a time, like in any image editor)

As you can see the Map consists out of several Layers.
Each Layer has several Cells.
Each Cell has variables called: dig, build, place, query.
(like the naming convention in Quickfort for using keystrokes within specific context)

These 4 variables should contain the keystrokes for Quickfort.
(nonsensical but syntactical correct Example: "b{Left}{Left}{Enter}")

and the Question is?
Which Datatypes / Collections should I use to make drawing the cells
effecient? I dont think I should use a Array like "Cell map[][][]"..
cause I have to go through every cell and probably most of them stay empty anyway..
There are many things like HashMaps, ArrayLists, Sets..
So what should I use?

Currently I have ArrayLists like this:
Is that it? or

Code:

ArrayList<Layer> map;

class Layer{
 ArrayList<Cell> content; //when using x,y in the cells
                          //I need to sort them too before exporting!
}

class Cell{
 int x, y;        //where on this layer is this cell
 String phase[3]; //0 = dig, 1 = build, ...
                  //a assoziative array would look nicer
}

I thought long and hard about this and I hope I dont step on anyones toes if I open up another thread asking something, but I well Im clueless. At this point I want to thank everyone again who reads this and/or tries to help
Thank you

[PleasingFungus]

Perhaps an oct-tree? (Wiki recommends R-trees, actually. Maybe look into those as well.)

[nikki]

I haven't got a cs degree so i'm sure there are nifty data container types out there that you could use and that i'm not aware of...

but anyway:

a few things:

i wouldn't use arraylists, you know the dimensions and they are not changeable during runtime, so a simple array should be faster.

A class that holds its own x en y variable is not neccesary either , you know the x and y because that's the index of the array. The strings you wnat to hold in an array over there can just as easily be ints or bytes , and thus you can put them in the array too

And finally:

As long as

(in the editor, as well as in the game you see one layer
at a time, like in any image editor)

this holds true i don't see the problem, you just show one 2d tile-map at a time and you can change the layer (tile map) you see,  you just change that map when it is neccesary (and load data from ram and lookup tiles or whatever)

Code:

type designer
   data:int[height,depth,width,variables]
   currentLayer:int=0


   method change_layer(v:int)
     currentLayer=v

   method draw_layer
     for local y:int= 0 until depth
         for local x:int = 0 until width
             do_draw(currentLayer,y,x) 
             local arr:int[4]=data[currentLayer,y,x] // pseudo pseudo
             use_variables(arr)

pretty naive/sketchy but roughly how it would do it 

[Zaratustra]

you might as well go the full monty and copy DF's storage method. DF marks each 40x40x1 block as empty or not.

In this case, you'd have a tridimensional array of blocks, each of which points either to null (meaning an empty block) or to a 40x40 array of tiles.

[Dacke]

What is the expected max size of a map? (max length, width, depth)

The super-easy way to do it is indeed a three-dimensional array. I would guess that it will require too much memory (as you suspected) but it wouldn't hurt to actually find out. Do you have the numbers?

[mesotes]

you might as well go the full monty and copy DF's storage method. DF marks each 40x40x1 block as empty or not.

In this case, you'd have a tridimensional array of blocks, each of which points either to null (meaning an empty block) or to a 40x40 array of tiles.

ah I see, the idea with the octtree makes sense now..
if thats how things are in game, then ill do that too
...

What is the expected max size of a map? (max length, width, depth)

The super-easy way to do it is indeed a three-dimensional array. I would guess that it will require too much memory (as you suspected) but it wouldn't hurt to actually find out. Do you have the numbers?

..well, the height and width of a layer wont be changed much, but layers will be added
fairly often I think. In the df magma wiki says there can be up to 600 z-levels (layers), but I think if I hard limit it to 200 there wont be any problems.
Maybe I can use a hard limit for width and height of 200 each for a layer too..
This seems the default map height/width used in DF chosing a embark site.
So its Cell map[200][200][200].
I guess I should try filling it up with random stuff to find out how much memory it uses?

Thanks for the input guys!

[Dacke]

Edit 1: I wrote a long post with code and everything. But it turns out I made a silly mistake. I will adjust this, but I need a bit more information.

The variables: dig, build, place, query.
How many different states can these be in?

Edit 2: restored the original post, with some edits
I have a feeling that 200 may be way too small. But if it really is 200, you may be able to get away with a 3D-array.

200³ = 8,000,000
If you want to save space, you could use a byte[][][], which will require approximately 8MB.
This will work if you have up to 4 possible values for each of the variables in each cell (dig, build, place, query).

If you want to have up to 256 different values for each variable, you can use the Cell object and have a byte for each.

Code that tests how much memory this will take:

Code:

public class Cell{
	byte dig, build, place, query;
	Cell(byte dig, byte build, byte place, byte query){
		this.dig=dig; this.build=build; this.place=place; this.query=query;
	}
	
	public String dig(){
		switch(dig){
			case 0: return "left";
			case 1: return "enter";
			default: return "";
		}
	}
}

public class DFTest {
	public static void main(String[] args){
		int width=200, length=200, depth=200;
		
		Runtime runtime = Runtime.getRuntime();
		long memoryBefore = runtime.totalMemory() - runtime.freeMemory();
		
		Cell[][][] space = new Cell[depth][width][length];
		
		long memoryAfter = runtime.totalMemory() - runtime.freeMemory();
		System.out.println(((double)memoryAfter-memoryBefore)/1000000+" MB required for empty array");
		
		for(int layer=0; layer<depth; layer++){
			for(int y=0; y<length; y++){
				for(int x=0; x<width; x++){
					space[layer][x][y] = new Cell((byte)7, (byte)13, (byte)99, (byte)-127);
				}
			}
		}
		
		memoryAfter = runtime.totalMemory() - runtime.freeMemory();
		System.out.println(((double)memoryAfter-memoryBefore)/1000000+" MB required for filled array");
	}
}

Output:
66.030232 MB required for empty array
257.615704 MB required for filled array
(random values gives the exact same memory requirement, but the code is a bit messier)

Result:
You may be able to use a 200³ array, if you use a byte to store the value. The class that wraps it add a bit.

If you just use four separate byte[][][], one for each variable, it will require 37.7 MB (empty and filled). This is well within acceptable limits, in my opinion.

You can use functions in the Cell-class to extract the corresponding Strings and/or colour-values.

[mesotes]

heh I already read your post and wanted to reply with this info.
its hard to tell, it depends on the variable..
like I said in my original post, these variables hold the keys which are pressed(easy example: dig hotkeys) or interpreted(example: stockpiles/place) by the Autohotkey Script of another program.

for dig its easy, there are 17 single hotkeys
so there should be only one char stored into a variable.

for build its a bit more complicated.
there are several groups in the menue so you need sometimes 2 characters
or modifiers like Shift or Alt to reach the option.
in all there are 78 unique states.
There is also one option which is a special case which is described below*.

for place its even more complicated.
this is where you place a stockpile which is as wide and high as
many keys are pressed.. I want to save already in a way to write
it directly into the Quickfort-readable .csv.
*The content will be a String looking like this: "f(2x5)"
So a "f"ood stockpile will be placed 2 tiles wide and 5 tiles high.
I cant think of a way to put that into a byte

for query.. uhm I really dont know.
its hard to look that one up since its a context sensetive operation
and the keys differ, depending on which workshop/furniture has been built.
What I do know is the content can be many characters long.
This may be the "biggest" variable, but the most unused one too!

Have a look here http://sun2design.com/quickfort/
to get an idea what the final .csv will look like and what it represents,
but I hope I explained it well enough already.

Also, I probably export this into a textfile for an easier way to extend the commands when new things are added into the game and the menue gets new hotkeys.

[Dacke]

OK, that's worse than I thought. I will restore my old post with some edits.

Just be aware that a char in Java is two bytes.

[Dacke]

Zaratustra's suggestion sounds very good. It's probably just as easy to implement as any byte-fiddling I'm trying to invent and it scales much better.

A second option is to only keep a few layers in the internal memory at the same time and load/save them from/to disc when needed. You can then use a naïve way to store each layer and still have plenty of space. If you store the current layer and 2-3 layers above and below, the user would be able to move up and down quickly. There could be loading times when jumping to a new position, but nothing terrible. Just put the loading in a separate thread (very easy in Java) and you'll be golden.

[mesotes]

Hm I think Ill do both.. for some extra practice. But Ill drop the byte stuff. Id rather not sacrifice readability of my own code than to have a little more RAM, which shouldn't be a problem nowadays.

Oh my, this sounds like fun

Thanks (again) Dacke & Zaratustra

[Dacke]

Sounds like an excellent plan.
If you run into any trouble or need a hand with something (like threading), just write another post here.

Also: When you keep making new threads, I have to keep hunting them down . If you could put all DF-paint-related things in one thread, I think you could get more consistent help.

[muku]

..well, the height and width of a layer wont be changed much, but layers will be added
fairly often I think. In the df magma wiki says there can be up to 600 z-levels (layers), but I think if I hard limit it to 200 there wont be any problems.
Maybe I can use a hard limit for width and height of 200 each for a layer too..
This seems the default map height/width used in DF chosing a embark site.
So its Cell map[200][200][200].
I guess I should try filling it up with random stuff to find out how much memory it uses?

If that's the case, you could store each layer in an [200][200] array (or indeed [200*200], for less indirections), and keep the individual layers in an ArrayList so that you can add new ones easily on demand. Or combine this with the sparse 40x40 block idea, if 200*200 per layer per default is too large for you.

[Dacke]

Just a minor side note:
I may be wrong, but I think [200][200] actually is faster than [200*200] in Java, when accessing/writing. The difference lies in [X][Y] and [X+Y*WIDTH], where the addition and multiplication take some time.

This is not really a problem, but I would encourage everyone to prioritize readability in code. At least my intuitions about speed-optimizations are often way off.

I would also want to distance myself from my big-array-idea. It scales so badly it will make the angels cry. It's probably better to write something non-hacky, to begin with, if it's going to be the base of a bigger program. In the future, the DF-fortresses will be bigger than the moon!

[mesotes]

Hello again, I coded long and hard on this and need some kind of "thats good" or "that sucks" on that Its not an actual Tree with nodes and stuff, but 2D Arrays.
I think I could do it a bit more dynamical with only one class.. but for now Ill leave it like this to get some feedback..

The next thing will be getting some basic drawing done with this new datastructure.

http://www.2shared.com/file/BEXD9pA_/src.html

btw: you can actually see something in the console!
you can also fiddle around with height and width in DFTest.java

Thanks for your feedback!

[nikki]

I'd start by using another service to upload to, datanest is nice and you can link directly (no annoying popups, windows, scary clicks) I don't have a java ide here so i couldn't compile...

what do the cellblock16 and cellblock32 do ?

why are there so many functions that return a specific tile (using modulus and member.methods) (couldn't you acces them directly ?)

I spotted some duplicated code, and was wondering how nested it was :


dftest has a 1d array of layers
   layer has a 2d array of cellblocks32
    cellblock has a 2d array of cellblocks16
     and cellblock16 has a 2d array of cells
       cell is the 'bottom' and has 4 strings...


I believe this could be organised a tad bit simpler and lighter, but that might be me.

btw:

But Ill drop the byte stuff. Id rather not sacrifice readability of my own code than to have a little more RAM, which shouldn't be a problem nowadays.

as long as you know you don't need values bigger then 255 then what's the problem ?
as soon as you start using bigger datasets (wich you want) why waste 4 times the RAM you need ? you could use that for something usefull instead

[mesotes]

Here is a little graphic to illustrate it a bit better..
I made it this way so I dont have to check for every little cell,
instead if I know a CellBlock32 is empty I dont need to look inside and
can draw a block of 32x32 white pixels instead..

So each Cell represents a pixel..
each CellBlock16 has a 16x16 Array of Cells
each CellBlock32 has a 2x2 Array of CellBlock16's (32x32 Cells)
and finally each Layer has a (width/32)+1 x (height/32)+1 Array of CellBlock32

Because of this structure, I cannot directly access a Cell..
I have to calculate which CellBlock32.. then which CB16 Block.. and finally the Cell itself..

Like I said earlier.. I think I could do that with only one class
but I think my heads gonna explode if I try doing that.
Im glad that it works somewhat right now.. :/

If I use bytes or strings isnt that important right now and can be
changed easily later on.


What other file hosts can you recommend for small files?

[Chromanoid]

i didn't read the whole thread... my two cents:
if you look at a 2d map with a screen you know all visible tiles of the map. this makes it very easy to draw. just determine the visible left top/right bottom of the tile map and go through it row by row. per each tile you go through the 3rd dimension and stop until you reach a visible tile. if you want to make it a bit faster you could store a first visible layer number per tile position. when you run the first time through the map you generate this on the fly. when the map is edited or some map layers are made invisible for editing purposes you can regenerate the first visible layer numbers per tile position...

[Dacke]

I haven't looked at the code, but I agree with your design choice. Having multiple classes makes sense, as the name of the class shows you exactly what it does.

It would be easy to change CellBlock16 and CellBlock32 to a more general CellBlock class. But if you know exactly what design you want, making it more general-case will only make things less stable.