On Nov 19, 2005, at 11:15 AM, Thomas Compter wrote:
I have a question that is not specific to RealBasic, but a general
game algorithm question.
I'd like to develop a game (in Realbasic and several other platforms)
that plays like the old Panzer General series of wargames.
Specifically, I would like when the player clicks on a unit, all the
hexes that the unit can move to are highlighted, so the player can
just then click on the desired destination hex. My design includes
the concept of movement points and terrain costs, so it's not as
simple as counting out a given number of hexes.
In my research on the net, I've heard discussion of "path finding"
algorithms, but they seem to be referring more to 1st person shooter
type games where the AI or game has to figure out the shortest path
between two given points. My problem is the inverse: I need to find
every location within range.
Path-finding refers to finding (usually the shortest) path between
two points on a map (game surface) which may have obstructions, and
applies to FPS games as well as to RTS (or even turn-based strategy)
games. The best algorithm seems to be the "A*" (A star) algorithm, and
you can find a discussions of this topic in a previous issue of RB
Developer (IIRC).
If you're just trying to find all coordinates that a unit can travel
to from a particular coordinate, then you need a depth-first search. In
general:
1) Find your SP (Starting Point)
2) Generate a list of all immediately adjacent points from that SP,
culling those that correspond to obstructions or impassable terrain, or
that fall outside the movement parameters for that unit, or that have
already been generated (you'll need a flag of some sort in each 'tile'
to mark if you've already visited it.)
3) For each point in the list generated in (2), recursively call the
algorithm in (2) above, then merge the resulting lists into a single
list for the next call.
4) You stop when all the calls to (2) result in null sets (lists) of
coordinates. This occurs when all the tiles are either; out of range of
the unit's movement capacity, or are impassable.
Note that for sparse maps (those with few obstructions or impassable
terrain tiles), or those that use hexes, this could be very
computationally expensive for units with a large movement radius!
Can anyone suggest or point me to an algorithm that would do what I'm
looking for?
Thanks.
_________
| homas
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://support.realsoftware.com/listarchives/lists.html>
William H Squires Jr
4400 Horizon Hill #4006
San Antonio, TX 78229
wsquires at satx dot rr dot com dot nospam <- remove the .nospam
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://support.realsoftware.com/listarchives/lists.html>
|