Hi !
Featured games (84)
games approved by the League of Dukes
Games in Showcase (595)
Games in Android Showcase (168)
games submitted by our members
Games in WIP (646)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Good way to calculate unit possible moves. (Tile)  (Read 2337 times)
0 Members and 1 Guest are viewing this topic.
Offline SpuTTer

Senior Devvie

Medals: 1
Exp: 14 years

Lazy Middle Class Intellectual

« Posted 2004-04-19 04:12:48 »

I've got a tile based map and I'd like to get a decent method to calculate all the possible squares that the  unit may move it.

Lets say that the unit can move 5 spaces.

Each tile has a movement 'cost'. So some tiles are harder than others to pass through.

Im trying to come up with a good method so that if you click on the unit, it will show all the possible locations the player can move.

I've been searching and I keep findind pathfinding A to B algorhythms, but nothing as general as what Im talking about.

I guess I could use A star and calculate the current player square vs every square on the map, but that seems wasteful.

I was trying to figure it out without posting here, but oh well. Hopefully someone else has done this before!

Thanks in advance!

Sacramento Volleyball
"Whitty phrase goes here."
Offline kevglass

« JGO Spiffy Duke »

Medals: 272
Projects: 25
Exp: 18 years

Coder, Trainee Pixel Artist, Game Reviewer

« Reply #1 - Posted 2004-04-19 04:43:24 »

You might want to try implementing a "dijkstra search", search google for it.

I've used it in the past with really good results in comparison to A*. However, you should also be able to use A* with a cap to work out just squares in a certain region.

A* code from Cas:;action=display;num=1037669044


Offline digitprop

Junior Devvie

« Reply #2 - Posted 2004-04-19 07:23:46 »

I would suggest the following (correct me if this is stupid): Use a recursive algorithm, always considering the four (or eight) tiles adjacent to the current one. Determine for each if the player can move onto it, and the remaining available 'movement points', based on the movement costs for the tile. Store the movement points for the tiles in a 2D array.

Then, do the same for each of the adjacent tiles as center tile. Keep track of already visited tiles, and replace the remaining 'movement points' for a tile if the already stored value is higher than the currently calculated value (in that case, you have discovered a cheaper route to the same tile).

If the 'movement points' for a tile change, make sure to recalculate all adjacent tiles (you may want to keep track of unvisited / to be recalculated tiles in a list), because their accessibility may have changed, too.

This may sound like a lot of processing, but in reality - depending on the costs of movement and the initially available movement points - the number of reachable tiles (and thus recursions) should be quite low.

M. Fischer .
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SpuTTer

Senior Devvie

Medals: 1
Exp: 14 years

Lazy Middle Class Intellectual

« Reply #3 - Posted 2004-04-19 14:40:13 »

Thanks to both of you. I had seen Cas' code, and researched the "dijkstra Algorhythm", but I wasnt sure if that would be applied to what I was doing becasue everyone always mentioned it for Point A->B.

I appreciate your idea as well digitprop. I was considering doing something similar, but wasnt sure if it was extremely inefficient.

More input appreciated. I will research Cas' code some more and look into doing my own method.

Sacramento Volleyball
"Whitty phrase goes here."
Offline D.t.O

Junior Devvie

Psych'd about Java Games

« Reply #4 - Posted 2004-04-20 03:11:55 »

I appreciate your idea as well digitprop. I was considering doing something similar, but wasnt sure if it was extremely inefficient.

It does sound inefficient at first, but it really depends on how far your unit is going to move. If the average move is, like in your example, only 5 spaces, then a simple KISS-style recursive algorithm should do the job. Depth first search (which I think this algorithm is) has, indeed, an exponential order of growth in terms of speed (not too much space is used though). Nevertheless, just like in the traditional Queens problem, the number of choices (again, this depends on how far a unit can move and how expensive the tiles are) will be relatively low at each step.

Now it sounds like I'm repeating what digitprop said. I guess I'm trying to say that Depth first search is not too bad if the number of choices dramatically decreases at some point.

EDIT: add some stuff:
Also, I don't think speed should matter too much, although it grows exponentially. Computers these days are relatively fast Smiley.
I think the only major problem you could encouter using this (or any) recursive approach is getting too big of a method call stack.

     - D.t.O
Offline SpuTTer

Senior Devvie

Medals: 1
Exp: 14 years

Lazy Middle Class Intellectual

« Reply #5 - Posted 2004-04-20 04:48:28 »

Thanks for your input. Im  thinking I'm going to try to implement something like you and digit are talking about. I'd rather have something easy and that I can completely understand rather than a complex algorhythm, at least for now.

Thanks for the tips.

Sacramento Volleyball
"Whitty phrase goes here."
Offline digitprop

Junior Devvie

« Reply #6 - Posted 2004-04-20 09:28:01 »

I would keep it as simple as possible if it is not obviously a severe bottleneck. You could even make it pluggable via an interface, so that you can later replace the algorithm easily - if you find that it takes up too much time.

'Optimize last', as the XP people say.

M. Fischer .
Offline SpuTTer

Senior Devvie

Medals: 1
Exp: 14 years

Lazy Middle Class Intellectual

« Reply #7 - Posted 2004-04-20 15:07:45 »

Yeah, that makes sense. I can always make it more robust later!!!


100th post ;o

Sacramento Volleyball
"Whitty phrase goes here."
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

deepthought (48 views)
2015-06-30 15:39:44

deepthought (55 views)
2015-06-30 15:39:09

deepthought (65 views)
2015-06-30 15:36:52

Za\'Anzabar (42 views)
2015-06-29 05:44:54

TritonDreyja (49 views)
2015-06-24 17:10:40

CopyableCougar4 (49 views)
2015-06-23 00:34:45

BurntPizza (55 views)
2015-06-21 20:36:46

cookiecompiler (94 views)
2015-06-11 15:42:53

cookiecompiler (56 views)
2015-06-11 15:41:14

NegativeZero (81 views)
2015-06-11 09:49:18
How Do I Expand My Game?
by bashfrog
2015-06-14 11:34:43

List of Learning Resources
by PocketCrafter7
2015-05-31 05:37:30

Intersection Methods
by Roquen
2015-05-29 08:19:33

List of Learning Resources
by SilverTiger
2015-05-05 10:20:32

How to: JGO Wiki
by Mac70
2015-02-17 20:56:16

2D Dynamic Lighting
by ThePixelPony
2015-01-01 20:25:42

How do I start Java Game Development?
by gouessej
2014-12-27 19:41:21

Resources for WIP games
by kpars
2014-12-18 10:26:14 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!