[Genrok]

I'm designing a battle engine for a game I'm working on, and I'm having problems. It's kinda like in Fire Emblim, where you click on one of your characters, then little blue squares light up on the ground, to show you where you can move. It's kinda hard because you have to avoid walls and stuff. Right now I'm making a robot draw out every possible move your character can make, but that takes up a huge amount of memory. Anyone know of an easier way to do it?

[Wervyn]

Probably. Last Generation in the latest DoZ did essentially that. The code was buggy, but that was mostly for the AI (later, private releases fixed this); the movement routine was intact. Still, I have no doubt that Exo put some complex work into that engine that may be above you, and it's not like anyone ever comments their MZX code.

To know more about how to help improve your engine specifically, I'd have to see your engine. I don't feel like writing my own from scratch right now, and I know that if I did you'd probably get something from me that's about as complicated (but ultimately flexible) as what you'd find in Last Generation.

"Aim for the stars. Settle for Pittsburgh."

[Exophase]

The worst part about those is AI. Good luck with that.

[LogiCow]

It's possible. The theory is fairly simple. It's not too processor-intensive either.

Basically, find an algorithm do do that first. Once you have that done, try to apply it to robotic.

[Sai'ke]

For an 2N by 2N grid around the player, set up a graph (a set of nodes (places you can stand) and edges that connect these nodes) where walls are represented by edges with a higher cost than your maximal number of walking points and use the Floyd-Warshall algorithm. N is the number of squares you can walk. I think for the all pairs problem this is the fastest unless you want to use fancy optimizations.

This will get you the minimal pathlength to each square with a complexity of O(n^3). You can then threshold the result by the number of steps you can take.

As Exo said, AI will surely give you headaches... xD

[Exophase]

The way I implemented movement in Last Generation is to recursively copy block the section until a new block for each of the four directions where not blocked, and then mark an arrow signifying which direction was picked. I expanded each one one at a time, so it was a list that grew recursively (potentially exponentially, but in reality most moves end up being blocked by barriers or old moves) at one end, then went through it linearly at the other end to perform the expansions. Eventually the linear iteration catches up with the expansion and you're done - all the blocks then contain valid movement paths. I also kept a master block which determines all valid movement destinations, for moving the player.

Now scoring these blocks (for AI) is another issue. I did that as I went and only kept the best scoring block (as opposed to all of them) on each iteration. How you determine score can depend on all sorts of things, but proximity to targets is a good one (near if you want to attack, far if you want to run away). A target can be a player or another enemy if you want to heal. You can throw in additional factors to weigh this about and you can make it dynamic. The important thing is having the means to score it in place, but coming up with good balanced scoring is actually really hard >_<

[Risu2112]

Have you considered making your battle engine an RTS instead of a TBS? The AI for the RTS would be far easier since the enemies would require much less foresight!

Whatever fits the game better though

[Genrok]

Ok, that gives me some ideas. Thanks!