Hood Organisation

What with expansions being limited, and new buildings coming out so frequently, it's more important than ever to make the most of your hood space.

Does anyone have a program which can help with this?

I know white frog's spreadsheet had something similar, but I don't think it was automated? A useful method might be:
1. Input the size of your hood
2. Input your buildings
3. Building sizes are stored in the program itself (eg gatling turret is 1x1)
4. The program then organises your buildings into a position which leaves large spaces free, and closes up small gaps.

Is this possible?

Thanks peeps :D

I haven't seen anything like this, and it would probably take quite a bit of programming. I will tell you that if you're running out of space, you should probably excise your worst few buildings, especially the larger ones.

Quote:

---

Originally Posted by kerching

Does anyone have a program which can help with this?

---

Everyone has a program for this - it's the grey matter located between your ears :p Seriously though, optimising your hood organisation is merely an exercise in patience and some trial and error.

Failing that, you could always go and look at some other player's hoods for some pointers.

Quote:

---

Originally Posted by AppleMacGuy

Everyone has a program for this - it's the grey matter located between your ears :p .

---

My grey matter is definitely not powerful enough for that :p

I'm just surprised that no-one's made one tbh. People here seem to have almost everything about the entire game covered!

I don't think the problem is figuring a program to fit blocks of space to a grid of space, but to do so in an optimal fashion. I mean, I've got all of my 12-hour buildings in a row (which still inexplicably get out of sync, thanks GREE), and my 24-hour buildings are fairly clustered together, but everything else is a mess. I've done a good job of cramming everything together, but I'd like for buildings that pay out in common multiples to be as close together as possible. It seems like a problem with no general solution.

Edit: another problem I see is if you did have an almost entirely packed hood, a new LTB might requiring rearranging the entire hood, which might not be possible if you don't have enough free space to shift buildings around.

Quote:

---

Originally Posted by AppleMacGuy

Everyone has a program for this - it's the grey matter located between your ears :p Seriously though, optimising your hood organisation is merely an exercise in patience and some trial and error.

Failing that, you could always go and look at some other player's hoods for some pointers.

---

Agree totally. Use brain, imagination and preferably some artistic sensibility

http://i1278.photobucket.com/albums/...ps0cd4d974.png

http://i1278.photobucket.com/albums/...ps89fe66eb.png

I think this is a kind of problem that is called "NP-hard" in computer science (its a "rectangle packing problem", a 2d version of the well known "bin packing problem"). As a result an optimal solution for big hoods it should not to be possible in acceptable running time (like: within your lifetime ...).

You can use an approximation algorithms to get a near-optimal solution. However, those that I know won't give you better results than placing them by hand with relatively simple strategies.

What I used to do is represent my total hood space as a grid in excel, and move coloured groups of cells around representing my buildings. Same as doing it in CC, but much quicker and less likely to accidentally sell something.

Can't be asked to do it anymore though. If I need space, sell ****ty buildings.

Quote:

---

Originally Posted by Lars

I think this is a kind of problem that is called "NP-hard" in computer science (its a "rectangle packing problem", a 2d version of the well known "bin packing problem").

You can use an approximation algorithms to get a near-optimal solution.

---

Umm okay, on it! Lmao!!

Quote:

---

Originally Posted by Lars

I think this is a kind of problem that is called "NP-hard" in computer science (its a "rectangle packing problem", a 2d version of the well known "bin packing problem"). As a result an optimal solution for big hoods it should not to be possible in acceptable running time (like: within your lifetime ...).

You can use an approximation algorithms to get a near-optimal solution. However, those that I know won't give you better results than placing them by hand with relatively simple strategies.

---

Something like this?

http://www.codeproject.com/Articles/...gorithm-for-bu

Or even this?

http://pollinimini.net/blog/rectangl...ng-2d-packing/

Quote:

---

Originally Posted by kerching

Something like this?

http://www.codeproject.com/Articles/...gorithm-for-bu

Or even this?

http://pollinimini.net/blog/rectangl...ng-2d-packing/

---

No, these are for packing rectangles into a single rectangle (as small as possible, but unbounded), not into a collection of rectangles (with fixed size).

More like this: http://users.cs.fiu.edu/~yzhan004/re...ing/survey.pdf

Or this: http://www.sciencedirect.com/science...66218X0100347X

There are hood planners in various spreadsheets. Look around.

Rectangle packing being NP hard doesn't imply anything about the problem for optimizing hoods in CC. No such classification means anything applied to a fixed size problem - they are about how the problem's difficulty grows with number of pieces. Here we have at most 80x80 space.

And the cc problem has many built in optimizations - every solution is equivalent over relative placement of say 6x6 buildings for example. And you can swap the hood blocks for each other. And each block has left-right or up-down symmetry, etc. I'm guessing a hood building planner would be quite possible. It just doesn't seem that useful compared to the work it would take, since doing this stuff in your head isn't very hard. Or just look at hoods that use space well.

Quote:

---

Originally Posted by zwiswoo

Rectangle packing being NP hard doesn't imply anything about the problem for optimizing hoods in CC. No such classification means anything applied to a fixed size problem - they are about how the problem's difficulty grows with number of pieces. Here we have at most 80x80 space.

---

I think run time will be n! for n the number buildings to be placed(*) (412 buildings for my hood -- not feasible). Having 'only' 6,400 grid points doesn't help; it's about the number of possible configurations which are not reduced by the grid layout. The grid just makes the configurations more regular but not smaller in number.

(*) If you have an approach with a significantly better run time I would be glad to hear it.

Quote:

---

Originally Posted by zwiswoo

And the cc problem has many built in optimizations - every solution is equivalent over relative placement of say 6x6 buildings for example. And you can swap the hood blocks for each other. And each block has left-right or up-down symmetry, etc. I'm guessing a hood building planner would be quite possible.

---

Yes, a specialized approach could take advantage of limited number of block sizes and it *might* help. However, I think it is by no means obvious it will. (It makes many configurations equivalent. I fear managing equivalences won't be faster here than to try out all combinations.) Also, industrial applications of 2d bin packing often have the same problem restriction and research community still work on small improvements for the approximate solutions for those cases ...

Blocks being horizontally and vertically symmetric won't help at all -- that's pretty much the default 2d bin packing (ie on axis parallel rectangles). Note that even 1d bin packing is already NP hard which is like the default 2d bin packing with boxes and blocks all having the same height, only different widths. And that is an even stronger restriction than just the symmetries in our case.

Quote:

---

Originally Posted by zwiswoo

It just doesn't seem that useful compared to the work it would take, since doing this stuff in your head isn't very hard. Or just look at hoods that use space well.

---

Agreed! :D

Lars, I agree a simple brute force over arrangements of 400 buildings is too slow. But that's not a fact about NP hardness or any other complexity class, which I think you'll agree are about asymptotics.

But the fact that buildings all come in one of 6-7 shapes seems like a fairly big reduction to this 400. Heck if you really have 400 (!) buildings I'm pretty sure you have 50 of at least 4-5 different buildings, and it makes no difference how you organize internally among them. More typically you'll see about 50-60 buildings in a small-ish hood, not 400 in a huge one, and with all the class reductions (2x2 4x4 6x6 6x5 etc) it seems like it could be quite tractable.

Anyway, tractable doesn't mean easy. I certainly wouldn't want to spend time writing such things :D