Distance Algorithims for Hex Maps (SOLVED)

BYOND Forums

Announcements · BYOND Help · Bug Reports · Feature Requests · Beta Testers · Beta Bugs · Developer Help · Design Philosophy · Demos & Libraries · Tutorials & Snippets · Art & Sound · Classified Ads · Game Updates · Contests & Events · Linux Talk · On Topic · Off Topic

ID:152232

Aug 19 2007, 8:18 am (Edited on Aug 19 2007, 10:24 am)

CriticalBotch

There are times I wish I was better at math, and this would be one of them.

For part of the game I'm working on there is a hex map. I use 1 tile hex turfs and set the x offset to 8*(map.maxx-src.x) and shift every odd hex (x=1, x=3, x=5, etc) down by 16 pixels (y offset = -16).

The tile outlay is fine, as you can see here:

The problem, as shown above, is that ranges work a tad . . . oddly. The pic above shows a range of 3 generated with a modified circle generator; it treats anything with an x larger than the src.x as being 1 higher. I've also tried circles, straight range(), etc. After mapping out on a pad of graph paper the tiles that I would need to generate something like this (range of 2):

I realised that the pattern was irregular. More specifically, for a range of 2 it needed to be

  #  
#####
#####
#####
 ###

A range of 3 was similar:

   #   
 #####
#######
#######
#######
#######
  ###

I haven't mapped out any other ranges, although I will if needed. What I'm trying to do is work out an algorithm that will take a range as a number and return a list of turfs in that range, as they appear on the hex map. I'm sure I can brute-force it but I'd rather finesse it, if possible. Any one out here dealt with something like this?

------------------------------------------------------
EDIT: Problem solved. I ended up going turf by turf in a line range tiles long from the centerpoint out in either direction horizontally, and adding a block of turfs 1 turf wide by (rng*2)+1-i, where i is the current iteration (1 to range), shifting up or down as needed.

Aug 19 2007, 8:46 am (Edited on Aug 19 2007, 8:54 am)

Xooxer

I have worked with a hex-based map before, though I think I did the opposite of you, and raised the even x tiles. Looking through my code, I don't see any distance or range calculations, but that doesn't surprise me. Just about all the action takes place between adjoining tiles, so i never needed to know what was 'over there'.

However, the illustrations of what your pattern looks like to the code seem almost exactly like the patterns I was finding in an isometric range I was trying to create. I tried many things, but no amount of clever maths on my part yeilded a correct rendering. So, I decided to take a simpler approach.

I suggest you define your own coordinate system to fit your hex map, then write your own procs to use this new coordinate layout to calculate your range and distance. Once you have a coordinate system that works, the code practically writes itself. Plus, you're not trying to do tricky math, since your grid matches your code, everything is simple to calculate, and runs faster than a convoluted formula.

~X

I know this may not help directly, but here are my iso procs to handle stuff like this. Once you have a working coordinate system laid out, these will probably help in writing your own procs.

atom
    var
        opaque
        base_layer
        iso_x
        iso_y
        list/iso_dither

    proc
        iso_initialize()
            base_layer = layer
            layer = world.maxy*2-y*2+base_layer
            iso_x = round(x/2)+y
            iso_y = round((world.maxx+1-x)/2)+y

        iso_inview(atom/Target)
            if(!Target) return
            var/list/L = line(Target.iso_x, Target.iso_y, src.iso_x, src.iso_y)
            for(var/n=1, n<=L.len, n+=2)
                var/turf/T = iso_locate(L[n],L[n+1],src.z)
                if(T)
                    if(T == src) continue
                    if(T.opaque)
                        return 0
                    for(var/atom/O in T)
                        sleep(-1)
                        if(O.opaque)
                            return 0
            return 1

        iso_update()
            iso_x = loc.iso_x
            iso_y = loc.iso_y
            layer = world.maxy*2-y*2+base_layer
            if(!(x&1)) layer--

turf
    terrain
        var/initial

proc
    iso_block(turf/Start, turf/End, z1, turf/x2, y2, z2)
        var/X1,Y1,Z1,X2,Y2,Z2
        if(isnum(Start))
            X1 = Start; Y1 = End; Z1 = z1
            if(isnum(x2)) {X2 = x2; Y2 = y2; Z2 = z2}
            else if(!isturf(x2)) return
            else {X2 = x2.x; Y2 = x2.y; Z2 = x2.z}
        else
            X1 = Start.x; Y1 = Start.y; Z1 = Start.z
            if(isnum(End)) {X2 = End; Y2 = z1; Z2 = x2}
            else if(!isturf(End)) return
            else {X2 = End.x; Y2 = End.y; Z2 = End.z}
        var/list/Block = new()
        for(var/iz = Z1, iz <= Z2, iz++)
            for(var/iy = Y1, iy <= Y2, iy++)
                for(var/ix = X1, ix <= X2, ix++)
                    var/turf/T = iso_locate(ix,iy,iz)
                    if(T) Block += T
        return Block

    iso_range(Dist, atom/Center=usr)
        var/list/Range = new()
        if(!isnum(Dist) || !isturf(Center.loc)) return Range
        var
            turf/T = Center.loc
            X1 = T.iso_x - Dist; Y1 = T.iso_y - Dist; Z1 = T.z
            X2 = T.iso_x + Dist; Y2 = T.iso_y + Dist; Z2 = T.z
            list/range = iso_block(X1,Y1,Z1,X2,Y2,Z2)
        for(T in range)
            Range += T
            Range += T.contents
        return Range

    get_iso_dir(atom/Loc1, atom/Loc2)
        var/Dir = 0
        if(!Loc1 || !Loc2) return
        if(     Loc1.iso_y < Loc2.iso_y) Dir += 1    // NORTH
        else if(Loc1.iso_y > Loc2.iso_y) Dir += 2    // SOUTH
        if(     Loc1.iso_x < Loc2.iso_x) Dir += 4    // EAST
        else if(Loc1.iso_x > Loc2.iso_x) Dir += 8    // WEST
        return Dir

    get_iso_step(atom/Ref, Dir)
        if(!Ref || !Dir) return
        switch(Dir)
            if(NORTH)       return iso_locate(Ref.iso_x,  Ref.iso_y+1,Ref.z)
            if(SOUTH)       return iso_locate(Ref.iso_x  ,Ref.iso_y-1,Ref.z)
            if(EAST)        return iso_locate(Ref.iso_x+1,Ref.iso_y  ,Ref.z)
            if(WEST)        return iso_locate(Ref.iso_x-1,Ref.iso_y  ,Ref.z)
            if(NORTHEAST)   return iso_locate(Ref.iso_x+1,Ref.iso_y+1,Ref.z)
            if(SOUTHEAST)   return iso_locate(Ref.iso_x+1,Ref.iso_y-1,Ref.z)
            if(NORTHWEST)   return iso_locate(Ref.iso_x-1,Ref.iso_y+1,Ref.z)
            if(SOUTHWEST)   return iso_locate(Ref.iso_x-1,Ref.iso_y-1,Ref.z)

    get_iso_dist(atom/Loc1, atom/Loc2)
        if(!Loc1 || !Loc2) return
        var
            xdist = abs(Loc1.iso_x - Loc2.iso_x)
            ydist = abs(Loc1.iso_y - Loc2.iso_y)
        return max(xdist, ydist)

    iso_view(Dist, atom/Center=usr) // TODO
        var/list/View = new()
        if(!isnum(Dist) || !isturf(Center.loc)) return View
        var/list/range = iso_range(Dist,Center)
        for(var/turf/terrain/T in range)
            sleep(-1)
            if(T.iso_inview(Center))
                View += T
                View += T.contents
        return View

    iso_locate(x,y,z)
        if(!(isnum(x))) return locate(x)
        else if(!isnum(y) || !isnum(z)) return
        var
            X = round(((world.maxx+1)/2)-(y-x),1)
            Y = round(x-(((world.maxx+1)/2)-(y-x))/2,1)
            Z = z
        return locate(X,Y,Z)

    line(x0, y0, x1, y1)
        var/steep = (abs(y1 - y0) > abs(x1 - x0)) ? 1 : 0
        var/east
        if(steep)
            var/t0 = x0, t1 = x1
            x0 = y0
            y0 = t0
            x1 = y1
            y1 = t1
        if(x0 > x1)
            var/t0 = x0, t1 = y0
            x0 = x1
            x1 = t0
            y0 = y1
            y1 = t1
        else east = 1
        var
            deltax = x1 - x0
            deltay = abs(y1 - y0)
            error = deltax/2
            ystep
            y = y0
            list/Line = new()
        if(y0 < y1)
            ystep = 1
        else
            ystep = -1
        for(var/x = x0, x <= x1, x++)
            if(steep)
                Line += y
                Line += x
            else
                Line += x
                Line += y
            error -= deltay
            if(east)
                if(error <= 0)
                    y += ystep
                    error += deltax
            else
                if(error < 0)
                    y += ystep
                    error += deltax
            sleep(-1)
        return Line

Aug 19 2007, 8:51 am (Edited on Aug 19 2007, 10:23 am)

Jtgibson

Well, evaluate the pattern of hexes:

Radius 1 (centre in odd column):
<code> ### ### # </code>

Radius 1 (centre in even column):
<code> # ### ### </code>

Radius 2 (centre in odd column):
<code> ### ##### ##### ##### # </code>

Radius 2 (centre in even column):
<code> # ##### ##### ##### ### </code>

[edit]I actually have these backwards, but the pattern still applies.[/edit]

If you continue the pattern indefinitely, you'll notice that even columns are the exact inverse of odd columns.

It looks as though the centre column is equal to (radius*2)+1 in length. The adjacent columns are (centre)-1, (centre)-2..., (centre)-(n) in length, up to 'radius' distant in either direction.

If I had more time, I'm sure I could try and come up with a basic idea of where to start from, but I have to go for now. I'll work on the problem a little later. In any case, though, I imagine the ultimate trick has to do with looking at the six endpoints of the hexagon that makes up the radius. You can then treat the whole thing as a system of inequalities, and anything that winds up being bounded by the outside edges of that hexagon is included in the results.

Or you can just solve it procedurally using that pattern, remembering that the hexes in the odd rows are shifted up or down depending on where the centre hex is.

Aug 19 2007, 9:00 am In response to Xooxer
CriticalBotch	Thanks Xooxer, I'll dive into those procs and see what I can come up with. I appreciate it!

Aug 19 2007, 9:02 am In response to Jtgibson
CriticalBotch	Thanks JT. I figured it was something like that but for some reason I couldn't get my head around it. This plus what Xooxer posted has provided me a lot of food for thought, thanks guys. If you do manage to come up with something before I do (quite likely), please let me know. Odds are I'll be busy banging my head against a wall, feel free to intrude :P Thanks again!