Limit Movement in TBS Game

ID:1555372
 
Apr 21 2014, 8:33 pm
(See the best response by Ter13.)
(There's a TL;DR at the bottom just in case it's needed)

So I have this little project I like to work on from time to time for fun more than anything. It helps me out whenever I need a break from a primary project, and may become something someday. I also enjoy the challenge of it, and up until this point I think I managed it pretty well, but now I'm stuck.

I honestly hate that I can't do this myself, but I can't even find the slightest clue. The problem is in the movement. I'm trying to set it up a lot like Fire Emblem games since I'm a fan of their movement system, but I can't even guess at how to subtract from the movement based off terrain type.

The general idea, for those not familiar with FE games, is that the player can normally only move X amount of tiles in a diamond shape where X is a characters movement limit. If a rough terrain comes into play, instead of costing 1 move, it should cost 2, etc. At least for most types of units.

Now I could probably do this if I had it going on a per movement basis, but the idea is to accurately display where all you can move from the moment you select the unit. It's much easier on the player. Another problem I for see is gonna be having things that are impossible to move to, and having to account for moving around them, much like moving through rough terrain.

So anyone have any ideas that might send me down the right track? I've included the most relevant part of my code at the bottom of this post, just to make things easier, prove I'm working on it, and avoid any concerns that I might be fishing for code.

I'm betting this is either really simple, or some advanced list thing I'm missing out on because I've still got a lot more to learn about them.

TL;DR

Fire Emblem Style movement. Can't figure out how to account for terrain like trees that should cost 2 movement instead of 1. Need to account for moving around obstacles too. All needs to be accounted for in highlight upon selecting unit, not per move. Any suggestions on how to make it work? Most relevant code I have so far is listed below.


//Snippet Credit to Shadowdarke (Slightly Modified)
proc
    no_diagonals_view(range, mob/center)
        var/list/L = view(range, center)
        for(var/turf/T in L)
            var/d = abs(center.x - T.x) + abs(center.y - T.y)
            if(d > range)
                L -= T
                L -= T.contents
            if(T.density == 1)
                L -= T
                var/image/I = image('redbox.dmi')
                I.loc = T
                usr << I
        for(var/turf/C in L)
            var/image/I2 = image('movebox.dmi')
            I2.loc = C
            usr << I2
        return L
//End Snippet


mob
    verb    //Just using verbs to test, clean up later
        select()
            if(!src.selectedunit)
                for(var/mob/M in src.loc)
                    if(M == src)
                        continue
                    src.selectedunit = M
                    src.movable = no_diagonals_view(M.moverange,M)
                    return
                //
            else
                if(src.loc in src.movable)
                    walk_to(src.selectedunit,src.loc,0,1,0)
                    spawn(4)
                        src.client.images = null
                    src.selectedunit = null
                    src.movable = list()

        deselect()
            src.client.images = null
            src.selectedunit = null
            src.movable = list()



Apr 21 2014, 9:29 pm
Best response
You are going to need to use a standard A* pathfinding approach, but instead of searching for a destination, you search alongside a heuristic.

proc
    get_move_range(turf/start,max_cost)
        var/list/moves = list(start)
        var/list/source = list()
        var/list/potential = list(start)
        var/list/costs = list(0)

        var/turf/t
        var/turf/test
        var/d

        source[start] = null
        costs[start] = 0

        while(potential.len)
            test = potential[1]

            for(d=1;d<=8;d*=2)
                t = get_step(test,d)
                . = t.move_cost + costs[test]
                if(t in moves)
                    //reassign more optimal paths
                    if(costs[t] <= .)
                        continue
                if(CAN_ENTER) //replace with a check to see if you can enter t from test
                    if(. <= max_cost)
                        if(!(t in potential))
                            potential += t
                        if(!(t in moves))
                            moves += t
                        source[t] = test
                        costs[t] = .
            potential -= test
        return moves


This is a pretty standard A* approach, except I quit processing nodes once I reach the max_depth I've arbitrarily assigned.

Again, though, you might want to generalize this behavior to a datum you can initialize, so you can retrieve more of the information this generates later on. If you loop through a destination point using the source array until you reach a null source turf, you can actually find the most-optimum path from the source to the endpoint that the player selects.

In addition to finding the endpoint, you can also get the movement cost by using the costs associative array with a key index of the destination turf.

This is far from a complete solution, however, as you will need to implement a test to see which turfs can be entered in the first place inside the loop where I put the comment indicating that.

I trust you are competent enough to put together the pieces yourself, though.
Apr 22 2014, 6:36 am
Ah, wow. I should definitely be able to piece it together now, yes, thank you!