[FuriKuri]

Okay, I'm working on a Fire Emblem-style game for MegaZeux (for those who dont know what that is, Fire Emblem is a turn-based strategy game, similar to that of Advance Wars). I pretty much have all of the unit types made, along with base stats, growth stats, max stats, and everything. Next, I wanna work on coding for moving units.

I have all of the ideas down, but the main problem I encountered is: move checking

Is there any kind of algorithm I can use for checking which moves are possible by a unit within a certain range, based on unit's movement range, so that it can be displayed as the unit is selected to move? (Kinda like how in FE, when you select a unit, blue boxes appear where the unit can move)

I just need to know how to calculate all of the spots the unit can move. I can then code it so that it displays all of these spaces.

[CJA]

I've tried an Advance Wars clone in MZX twice, and this is where I always get stuck.

The only thing to do is count out every single possibility of directions.

[Dr Lancer-X]

Really easy to do--just use recursion and try each direction until the max distance has been reached, recording reached tiles. Try to keep move distances low if you do this, though.

[RoSS]

If there aren't terrain penalties, this will work:
If you want to see whether a specific location is within dist, you should probably just do
if "('abs(&locx& - &charx&)' + 'abs(&locy& - &chary&)')" <= "dist"

If you want to check all spots, you can do something like

loop start
set "checky1" "('chary' - 'dist' + 'loopcount')"
set "checky2" "('chary' + 'dist' - 'loopcount')
set "checkx" "('charx' - 'loopcount')"
: "lp"
. "do whatever your check is to see if there's an open space at checkx, checky1 and checkx,checky2"
inc "checkx" 1
if "checkx" <= "('charx' + 'loopcount')" "lp"
loop "dist"

What that code is doing is creates that "diamond of movement" that you see in strategy games. Since it is symmetric, you can check the top half and the bottom half at the same time. Checkx,Checky1 represents a point to check on the top half and checkx,checky2 represents a point to check on the bottom half.

However, if there's terrain penalties, this won't work and you'll have to do it lancer's way. Unfortunately, he didn't write any code for you and MZX doesn't handle recursive stuff super-nice and I don't really feel like coding it =P

[hob nado]

Do MZX subroutines actually work based on a stack and thus support recursion? I've never tried it...

[Dr Lancer-X]

Of course, how else would they work?

[Koji]

Yes, subroutines involve a stack, it used to be limited to like 10 recursions deep, but exo has since updated the stack to a linked list and thus making the depth infinite (or at least much deeper than you should ever exploit)

And for a good example of a recursive flood fill try my (dated) A* engine in the engines section

A* is a path finding routine that starts from either the end point the start point or both simotaneously and carries out a routines that spreads a trail in every possible direction untill one spreading group runs into the destination start or the other spreading group and then the SHORTEST possible path between the two points is found.

Anyway the FIRST part is what you're interested in, how to recursively spread from an origin. My engine was simple. There was 2 constructs and a single routine preformed on the constructs.

constructs:
1) Blocked list (the actual physicial map was used)
2) Node list (the nodes, more on that later)

The first node was designated to the start position.
from there the routine starts

What the routine does is for every node is looks around for not blocked areas (by means of the blocked list) that were either n/s/e/w from the node's position, define nodes on the list for thoes places, and then set the current nodes position as blocked (to prevent useless redundant back tracking paths of resource hoggingness).

Anyway to make the routine spread out to a specific range... you could have the routine calculate the distance of the current node from the start, and if it's over a certain distance, it escapes from the routine.

Of course this was all before subroutines were implimented into mzx, so you could probably come up with a much faster way to pop between nodes and know the distance without the calculation using subroutines.

Good Luck

[FuriKuri]

Okay, got it...took me a while, but I implemented an algorithm that is similar to CJA's idea.

What I did was create a stack of values: X, Y, and Cost. I made an imaginary box around the unit, with the unit centered in the box, the box having a width two times the unit's range, plus one. Each space in this box was set to a cost of "-1", meaning it couldn't be reached (so far). Then, starting from the unit's position, it checked the terrain next to it in each four directions, to check if passable, or if it can be passed with its cost. Then, a new cost is set to that space (i.e. changing the -1 to something like 5), and that space is added to the list of spaces that can be reached (in a new variable list), and then added to the list of spaces to be checked. If a space already checked is checked again, it will not be replaced unless if the cost to reach was lower, therefore checking possibilities of further spaces that can be reached. Afterward, when the last item of the list is checked and no other space is added to the checking list, spaces that are legal to move to are displayed (in my game, spaces will be highlighted blue).

Right now it's kinda messy, but once I clean up the test board a bit, and set up a sample map to test movement, I'll upload the demo and show how it works ^_^

EDIT: Due to the long checking process, even at high mzx speed, it takes ~4 seconds to calculate legal spaces (spaces are displayed in a split second)...I'll definitely have to make the code a little more efficient, and find a way to speed up the process.

This post has been edited by FuriKuri: 24 March 2007 - 01:36 AM

[FuriKuri]

Okay, everything works fine with the movement, but now that I finally have free time to work on FE again, I've come across a new problem...how the opponent should decide their moves.

I've made it so they check each space within range, and calculate each of those spaces priority values. To calculate these values, priority would increase if the unit was a lower level or weaker, and would decrease if stronger or higher level. Priority would also increase if the unit could not counterattack, or was at a disadvantage (higher decrease though for no counterattack). Any healing units, such as clerics who only use staves, would be a high priority as well, since they can't attack at all. Also, terrain bonuses would be taken into consideration as well. After calculation, the space with the highest priority would be determined, and the unit would move to that space, making their attack if possible.

I just need to know what values I should use for this calculation...I've come across a rough guess so far (at the end of calculation, highest value is highest priority):

Level: (opp. unit lvl - target unit lvl) x 3
+ HP: (opp. unit HP - target unit HP)
+ Counter?: +10 if cannot counter, +5 if opponent has wpn triangle advantage, -5 if disadvantage, +15 if healer
+ (opp. unit hit rate) / 8

For level, +20 if upgraded unit (i.e. Lvl 3 Sniper would be lvl 23 in this case)

So for example, the opponent has a Lvl 12 Cavalier using Steel Lance with 26 HP, and targets a Lvl 13 Archer using Steel Bow with 18 HP:

Level: (12 - 13) x 3
HP: (26 - 18)
Counter?: +10
Hit Rate: 11 (assuming hit rate for opponent was 88)

-3
8
10
+11
-----
26


So the priority for the target is 26, and if no other targets have a higher priority, the Cavalier would move and attack the Archer.

I'm still thinking about doing hit rate, but if any of you have any ideas on how to adjust this or add new values, I'd appreciate it ^_^

[Val]

Off-topic, but you really should consider making your sig image smaller. It's taking up a lot more space than it should be.

[T-Bone]

I think that sig is amazing

[CJA]

it was different then

[Koji]

DID YOU KNOW THAT:
Games with little resources for AI often cheat?
NOW YOU KNOW!

Your game probably has a fog of war, but you know what's more annoying than a fog of war, waiting for a poor AI to find you in a fog of war D:<

The AI either should have to deal with the fog of war and have a perfect view of where everything is, or it should be naturally attracted to the fogged spaces if there isn't something unfogged it finds more interesting

several different AI designs are available for RTS's a mixture of these is probably best

1) Goal based: think of it like this, the AI has a to do list, (each level or enemy you run into may have DIFFERENT to do lists) the to do list might be something like "do NEAREST item: capture town, explore fog, attack enemy" Where capturing towns is it's main deal, exploreing fog is second and as if nothing else attack an enemy. these options should probably onlybe available about items within a certain range of the enemy) Similarly the WHOLE LEVEL could have a todo list such as "make infantry cature these towns, make tanks, storm the player by shortest pathwhile keeping infantry back up in the wooded areas progressing toward players towns." Stuff like that.

2) Scoring AI: using a formula to decide the BEST corse of action, this is harder to attribute to an RTS about movement, but it would aid in picking things to attack, or towns to capture.

3) Event Based: If player does this, do THIS in responce. This AI is usually the easiest to beat because you can learn the pattern and exploit it. However it can be good for defense AI.

4) State engine: This isn't so much AI in itself but a good way to switch between AI algorithims, it has some calculation to determine what STATE the game is in and choose an AI algorithm to fit it. it could be something as simple as "If player has more enemies than I do, produce more enemies, if player is near, defend, if player is far, capture towns and fortify choke points if player has less enemies than I do, offensive storm"