Turn-Based Movement Algorithm

Kezarus

Endless Game Maker
Hello everyone!

Just posting my turn-based movement code for the ones that might need it.

First of, there are other codes besides just the movement, like enums and constants, but I think you can figure it out.

Call this to comence the move nodes
GML:
function CharCombatMove(charId){
    CharCombatMoveFill(charId, charId.x div COMBAT_CELL_SIZE, charId.y div COMBAT_CELL_SIZE, 0, noone);
}

This is a recursive function to place all Move Nodes
GML:
function CharCombatMoveFill(charId, cellX, cellY, totalCost, cameFrom){
    //STAY WITHIN BOUNDS
    if( cellX < 0 || cellY < 0 ||
        cellX >= room_width div COMBAT_CELL_SIZE ||
        cellY >= room_height div COMBAT_CELL_SIZE ){
        return;
    }
  
    var cost = 1;
    if( cameFrom == noone ){ //STARTING POINT COST
        cost = 0;
    }else{
        cost = CombatMoveGetSquareCost(charId, cellX, cellY);
    }
    if( cost == -1 ){ return; } //BLOCKED TERRAIN
    totalCost += cost;

    //NOT ENOUGH MOVEMENT TO REACH IT
    if( totalCost > charId.moveNow + charId.dashNow ){ return; }
  
    //CENTER OF SQUARE
    var wx = (cellX * COMBAT_CELL_SIZE)+(COMBAT_CELL_SIZE div 2);
    var wy = (cellY * COMBAT_CELL_SIZE)+(COMBAT_CELL_SIZE div 2);
  
    var moveNode = collision_point(wx, wy, objMoveNode, false, false);
    var cantClick = false;
    if(moveNode == noone){
        moveNode = instance_create(wx, wy, objMoveNode);
        cantClick = position_meeting(wx, wy, objCharCombat); //SET NODE ON TOP ANOTHER CHAR AS UNCLICKABLE
    }else if(moveNode.totalCost <= totalCost){
        return;
    }else if(moveNode.totalCost > totalCost){
        //FOUND A BEST PATH
        //WILL BE SET BELOW
    }

    moveNode.owner = charId;
    moveNode.totalCost = totalCost;
    moveNode.cameFrom = cameFrom;
    moveNode.cantClick = cantClick;
    if(moveNode.totalCost > charId.moveNow){
        moveNode.isDash = true;
    }else{
        moveNode.isDash = false;
    }
  
    CharCombatMoveFill(charId, cellX+1, cellY+0, totalCost, moveNode);
    CharCombatMoveFill(charId, cellX-1, cellY+0, totalCost, moveNode);
    CharCombatMoveFill(charId, cellX+0, cellY+1, totalCost, moveNode);
    CharCombatMoveFill(charId, cellX+0, cellY-1, totalCost, moveNode);
}

It returns the cost of a square or -1 if it's blocked by something
GML:
function CombatMoveGetSquareCost(charId, cellX, cellY){
    //returns -1 if blocked
    var wCost = 1; //STANDARD

    //GET SNOW COST
    if(objCombatManager.grdSnow[# cellX, cellY] != -1){
        wCost += 1;
    }

    //GET TERRAIN COST
    var wx = (cellX * COMBAT_CELL_SIZE)+(COMBAT_CELL_SIZE div 2);
    var wy = (cellY * COMBAT_CELL_SIZE)+(COMBAT_CELL_SIZE div 2);
    var inst = collision_point(wx, wy, objDodats, false, false);
    if( inst != noone ){
        if( inst.type == DodatsEnum.Bushes || inst.type == DodatsEnum.Rocky ){
            wCost += 1;
        }else if( inst.type == DodatsEnum.Tree || inst.type == DodatsEnum.BigRock ){
            wCost = -1; //BLOCKED
        }
    }
  
    //ACCOUNT FOR ALLIES AND ENEMIES
    var otherChar = collision_point(wx, wy, objCharCombat, false, false);
    if( otherChar != noone ){
        if( charId.Team != otherChar.Team ){
            wCost = -1; //BLOCKED
        }
    }
  
    return wCost;
}

GML:
image_blend = c_blue;
image_alpha = 0.75;
depth = -y+2;

totalCost = 0;
cameFrom = noone;

mouseOver = false;
isDash = false;

owner = noone;

alarm[0] = 1;

cantClick = false;

GML:
/// @description CONSTRUCTOR
if(isDash){
    image_blend = c_red;
}

if(cantClick){
    visible = false;
}

GML:
draw_self();

if( mouseOver ){
    depth = -100000;
    var lastNode = id;
    var wCameFrom = cameFrom;
    while( wCameFrom != noone ){
        draw_set_color(c_blue);
        draw_set_alpha(1);
        draw_line_width(lastNode.x, lastNode.y, wCameFrom.x, wCameFrom.y, 10);
      
        lastNode = wCameFrom;
        wCameFrom = lastNode.cameFrom;
    }
  
    draw_set_font_ext(fntStandard, c_yellow, fa_center, fa_middle, 1);
    draw_text(x, y, totalCost);
}

GML:
/// @description ADD PATH
if( !cantClick ){
    //GET PATH
    var path = [];
    var wCameFrom = id;
    do{
        array_push(path, [wCameFrom.x, wCameFrom.y]);
        wCameFrom = wCameFrom.cameFrom;
    }until(wCameFrom == noone)


    with(owner){
        //SET PATH
        movePath = path;
  
        //DECREMENT MOVE
        if(other.totalCost <= moveNow){
            moveNow -= other.totalCost;
        }else{
            var cost = other.totalCost - moveNow;
            moveNow = 0;
            dashNow -= cost;
        }
  
        alarm[1] = 1; //MOVE START
    }

    instance_destroy(objMoveNode);
}

GML:
mouseOver = true;
image_alpha = 1;

GML:
mouseOver = false;
image_alpha = 0.75;
depth = -y+2;

This moves the Char
GML:
/// @description MOVE
alarm[1] = 1;

//NO DESTINATION
if( moveToX == -1 ){
    //BUT I HAVE WHERE TO GO
    if( array_length(movePath) > 0 ){
        var arr = array_pop(movePath);
        moveToX = arr[0];
        moveToY = arr[1];
    }else{
        //END OF PATH
        alarm[1] = -1;
        speed = 0;
        CharCombatMoveEnd(id);
    }
}

var speedNow = moveSpeed; //TODO: PUT MODIFIER HERE FOR GAME SPEED UP
if( moveToX != -1 ){
    if( point_distance(x, y, moveToX, moveToY) <= speedNow ){
        x = moveToX;
        y = moveToY;
        moveToX = -1;
        moveToY = -1;
        speed = 0;
    }else{
        //REAL MOVE
        move_towards_point(moveToX, moveToY, speedNow);
    }
}

Feel free to ask me anything. I hope this helps. =]
 
Last edited:

GMWolf

aka fel666
looks pretty neat! the path finding just looks like a recursive version of dijkstras. I think you would be better off just using dijkstras there, as the priority system will avoid considering the same nodes over and over.
Having a fast path finding algorithm becomes really useful when implementing AI. (In fact I turned away from GM when i couldnt get my path finding fast enough for the type of AI I was writing (GOAP), In retrospect using another form of AI, or simply writing a DLL would have been better than my 4 year journey switching between various custom built engines).

one thing i found very useful for the actual movement of the characters is using an Actor-Action system. It just keeps a lot of the different details out of the main object. That video was actually written after I implemented that system in my own prototype.
Also linking those actions together by having a "next action" field was extremely powerful. I could use it for moving from tile to tile, but also chaining animations like move, then attack, compute HP, <optional kill character> etc. Actions could conditionally insert more actions down the chain etc. A very powerful and flexible system. A downside to this is following the flow just from reading code is not as straight forward. If most of your entities do the same sort of stuff, then a simple script will probably be best.

This is my humble code guys. Is it any good?
Yeah, its quite neat. Again, i think dijkstras is likely a better fit, but that's really my only note.
The cameFrom structure is the exact structure Ive used over and over, never had any issues with it.

I would also recommend researching stack based state machines. Thats how I mostly ended up structuring my game flow. unfortunately its not perfect, and will not cover every situation (I think the next incarnation of my prototype will just embrace the stack flow in the design because I havent found a better alternative... yet (on going research)).

(you kinda motivated me to get going with my project again, I dont want to get left behind haha!)
 
Last edited:

Kezarus

Endless Game Maker
@GMWolf, thanks a lot for the feedback, mate!

Hmmm, I messed around dijikstra's before. That recursion I just could pull out of the top of my head. I don't know why I didn't used dijikstra's here. 😅

My last game used a lot of "brute force" and air-tight objects. Like, every object and function did one thing and one thing only. That helped me a lot in isolating bugs. I knew exactly where I could find them. Also my brother is a 10th Dan Black Belt Quality Assurance. The bastard can find an issue in no time. XD

I don't know if what I do have a name, I base my development on having one Controller object that call other objects and is called back when the objects finish whatever they were doing. Works pretty good. I will post the code here from time to time.

What motivates me it to be around good people like you all here on the forum. =]

Let's game on, mates!
 

TsukaYuriko

☄️
Forum Staff
Moderator
The Tutorials forum has its own rules and template, this topic would need to follow that for it to be moved there. ;)

I'd suggest to rework it accordingly, then post a new topic in the Tutorials forum which will then go through the standard approval process. This topic can then be closed.
 

GMWolf

aka fel666
Yup if the purpose was sharing the code as an example, tutorial is a good fit.
But if this was more of the discussion type topic, wouldn't Advanced programming be a better fit?
 
Top