Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 [2]

Author Topic: Circles in Grids  (Read 7258 times)

Urist Da Vinci

  • Bay Watcher
  • [NATURAL_SKILL: ENGINEER:4]
    • View Profile
Re: Circles in Grids
« Reply #15 on: March 07, 2011, 11:55:58 am »

...That in no way helps me draw a circular fortress...

OK, I misread what you originally posted.

The http://neil.fraser.name/news/2006/11/17/ from the linked thread looks best to me. I like using the 112 xyz proportions, since I like to assume that the x,y,z dimensions of a tile are 5ft x 5ft x 10ft.

In the past, since there wasn't a program availiable to do this, I drew a quarter-circle of the correct radius on graph paper and shaded in tiles along the line at the edge by hand. That also allowed me to fill diagonal holes in the wall.

Girlinhat

  • Bay Watcher
  • [PREFSTRING:large ears]
    • View Profile
Re: Circles in Grids
« Reply #16 on: March 07, 2011, 12:15:25 pm »

Worryingly enough, I've got three things open.  One is a picture the Minecraft guy linked, another is the Neil Fraser sphere maker, and the third is the html page that I downloaded from that other thread.  Each of them gives different shapes for any given size...

ZCM

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #17 on: March 07, 2011, 12:53:49 pm »

Well, you can't draw a perfect circle using grid blocks; it's obviously impossible. You can only get "circle-like", and depending on how you define "circle-like", you can get different shapes for the same size.

If you really want to compute them by hand, Pythagoras's Law works as well as anything.
Logged
Badger badgers badger badger badgers badgers badger.

MarcAFK

  • Bay Watcher
  • [INSANITY INTENSIFIES]
    • View Profile
Re: Circles in Grids
« Reply #18 on: March 08, 2011, 01:12:23 am »

Get some graph paper and draw a circle on it with a compass at the radius you want...
Or use squares
Logged
They're nearly as bad as badgers. Build a couple of anti-buzzard SAM sites marksdwarf towers and your fortress will look like Baghdad in 2003 from all the aerial bolt spam. You waste a lot of ammo and everything is covered in unslightly exploded buzzard bits and broken bolts.

ahonek

  • Bay Watcher
  • Tekeli-li! Tekeli-li!
    • View Profile
Re: Circles in Grids
« Reply #19 on: March 08, 2011, 08:29:29 am »

Resource for making spheres using voxels:

http://www.hardijzer.nl/MinecraftSpheres.html

This was designed to make three dimensional spheres in Minecraft, but you might find it useful for Dwarf Fortress as well.
Logged

MarcAFK

  • Bay Watcher
  • [INSANITY INTENSIFIES]
    • View Profile
Re: Circles in Grids
« Reply #20 on: March 08, 2011, 08:33:15 am »

those are just squares with corners cut out...
Logged
They're nearly as bad as badgers. Build a couple of anti-buzzard SAM sites marksdwarf towers and your fortress will look like Baghdad in 2003 from all the aerial bolt spam. You waste a lot of ammo and everything is covered in unslightly exploded buzzard bits and broken bolts.

ahonek

  • Bay Watcher
  • Tekeli-li! Tekeli-li!
    • View Profile
Re: Circles in Grids
« Reply #21 on: March 08, 2011, 08:36:04 am »

Change the radius of the sphere and you get better shapes.
Logged

languard

  • Bay Watcher
  • Meep
    • View Profile
Re: Circles in Grids
« Reply #22 on: March 08, 2011, 10:14:55 am »

And yet one more way.

Load up Gimp, use the circle select tool and turn off anti-aliasing.  Start dragging out the selection, then press and hold shift.  This locks the shape into a perfect circle.  It will show you the size in the status bar.  Drag it out to the desired size, and then use the paint tool to fill it.  Turn on the grid and configure it to a 1 pixel grid.  Have fun counting squares :P  You can do some interesting designs this way.

I think somewhere there's a tool that can turn pngs into macros, but it's been a while and I don't remember what it was called.
Logged
He's now moping around, doing Armok knows what. As far as I can tell he's just going to stay there, in the party room. Forever.
Given our relationship thus far, I can genuinely say the party has just begun for me. - Captain Mayday,

ZeroSumHappiness

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #23 on: March 08, 2011, 11:16:52 am »

The reason different programs give different results is because they define what constitutes inside and outside of the circle differently.

The easiest way of determining in or out would be the following:
1. Define a square as the "center" of your circle.
2. Define a radius.
3. All target squares where the Euclidean distance between the midpoint of your central square and the midpoint of the target square is less than or equal to the radius are in the circle.

(This extends to three dimensions easily, since Euclidean distance maintains definition.)

This will give you an odd-sized circle.

Other measurements you could use would be to take an intersection of four squares and measure the Euclidean distance from that intersection to the midpoints of squares.  Defining your radius there is important.  You could also use the distance from your intersection to the farthest corner, or the closest corner.  Or the radius has to contain three corners, or just two corners.
Logged

Starver

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #24 on: March 08, 2011, 11:41:38 am »

The reason different programs give different results is because they define what constitutes inside and outside of the circle differently.

[...]

You could also use the distance from your [centre, of either kind] to the farthest corner, or the closest corner.  Or the radius has to contain three corners, or just two corners.
Or go for tiles with more than half covered by the circle, in which case are you approximating a straight line between the two intersections or actually calculating the bulging arc.  And though this would cover an absolute minority of cases, is it >0.5 or >=0.5?

Alternatively, anything completely within the circle is not the circle wall.  Anything completely outside of the circle is not the circle wall.  Anything lying on the circle (and possibly you need to fudge things if you get the circle intersecting a four-tile intersection, leaving a diagonally-navigable passage, as you would, frexample, from a radius five circle, based upon a four-square intersection, at the eight different points represented by the interchangable coordinates {+/-3,+/-5}) and from that you get a wall.  Albeit it looks far better at large scales.


Yes, different systems will use slightly different methods.  Use what looks good.  Or an alternative (not exactly equivalent) philosophy is if it looks good, use it. :)
Logged

ZeroSumHappiness

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #25 on: March 08, 2011, 11:42:59 am »

The problem with using "half" is that you have to do an area calculation, which is annoying.  I mean, I could work out the math, but it's a lot more complex than doing a distance to a point within.  You could Monte Carlo it easily enough though.
Logged

j0nas

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #26 on: March 08, 2011, 11:48:40 am »

I think somewhere there's a tool that can turn pngs into macros, but it's been a while and I don't remember what it was called.
Quickfort?

The problem with using "half" is that you have to do an area calculation, which is annoying.  I mean, I could work out the math, but it's a lot more complex than doing a distance to a point within.  You could Monte Carlo it easily enough though.
I Monte Carlo'd it, and it's probable that you don't really know what you're talking about.
Logged

Jeoshua

  • Bay Watcher
  • God help me, I think I may be addicted to modding.
    • View Profile
Re: Circles in Grids
« Reply #27 on: March 08, 2011, 11:54:33 am »

Chromafort.  It turns image files (and I think, not just pngs) into Quickfort files.  Which you can put into Quickfort and auto-designate once you're done.

So you're not wrong, but half right.

Note: Quickfort doesn't do so well with above ground multi-level constructions.  It will fail to designate the upper levels due to there not being access to building materials (can't build level 2 until you build level 1).  So do take that into consideration when using it... unlike me.
Logged
I like fortresses because they are still underground.

ZeroSumHappiness

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #28 on: March 08, 2011, 11:59:17 am »

I Monte Carlo'd it, and it's probable that you don't really know what you're talking about.
Wait, what?  Did I miss a sarcasm tag?
Logged

Starver

  • Bay Watcher
    • View Profile
Re: Circles in Grids
« Reply #29 on: March 08, 2011, 12:05:43 pm »

The problem with using "half" is that you have to do an area calculation, which is annoying.  I mean, I could work out the math, but it's a lot more complex than doing a distance to a point within.  You could Monte Carlo it easily enough though.
For the straight-line approximation, it's fairly easy.

  • If intersections are exactly on opposite corners then it's half-n-half.  That'd be essentially the four 45 degree points, with a radius having some sort of integer/integer-and-a-half multiple of root2, if I've juggled the permutations in my head, correctly.
  • If intersections are on adjacent sides (including one or both on corners, so long as those corners are not opposite ones), then it's not half-n-half (whether it's the far-from-radius adjacent sides or near-to-radius adjacent, to work out which fraction is the better one)
  • If the intersections are on opposite sides (and that would be circumferentially opposite, not in any way radially) then the average fraction of the primarily-radial side-length of the intersections will be the fraction of the area covered by the straight-line division of the tile between these two intersections.  (This case also covers adjacent corners both intersected ((see the special case mentioned below)), in which case your approximate radius actually covers none/all of the tile, according to which adjacent edges that would be.)

Having to integrate for the area under the curving line is of course most difficult, but about the only time that this matters if it's a low-radius circle, and in particular where it crosses the four tiles (assuming the radius is measured from the centre/centre of a tile) exactly on either axis, thus with tile-boundary intersections both below the high-point of the arc.  In fact, the arc could intrude into the area 1 tile further away from the origin.

So it depends on how picky you are.  But for the likes of the large circles I take it can't be easily modelled with zoomed-in-paint (although I'm sure I could do circles up to several hundred in size without too much fuss, even without GIMP's "make this oval circular" method), it'd be close enough for government work, right?
Logged
Pages: 1 [2]