Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (495)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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  
  A* with wall based tiles  (Read 1420 times)
0 Members and 1 Guest are viewing this topic.
Offline sproket

Junior Member


Medals: 1



« Posted 2013-01-28 21:49:58 »

Hi guys,

I've been trying to build a path finder for my game. As you can see by the pic below, this is using walls instead of simple blocks. I'm not sure how this is affecting the algorithm.  Samples I've seen use tiles where each coordinate is either blocked or not. In my case each coordinate may be blocked only from a particular direction.

Any tips on how I could do the algorithm differently?



Offline sproingie

JGO Kernel


Medals: 202



« Reply #1 - Posted 2013-01-28 21:56:19 »

A* should still work the same.  When you generate the neighbors, you just exclude any for which there's a wall in the way.
Offline Best Username Ever

Junior Member





« Reply #2 - Posted 2013-01-28 21:59:48 »

The algorithm itself does not need to be changed. A-star can work on any type of graph. A grid is a graph. Graphs have nodes and edges. Nodes are the places your search algorithm can visit. Edges are the connections between nodes.

Empty grids have graphs like this:

1  
2  
3  
4  
5  
6  
7  
+E+E+E+E+E+E+E+E+E+E+
E E E E E E E E E E E
+E+E+E+E+E+E+E+E+E+E+
E E E E E E E E E E E
+E+E+E+E+E+E+E+E+E+E+
E E E E E E E E E E E
+E+E+E+E+E+E+E+E+E+E+


Grids with occupied squares have graphs like this

1  
2  
3  
4  
5  
6  
7  
+E+E+E+E+E+E+E+E+E+E+
E E E   E E E E E E E
+E+E+   +E+E+E+E+E+E+
E E E   E E E   E E E
+E+E+E+E+E+E+   +E+E+
E E E E E E E   E E E
+E+E+E+E+E+E+E+E+E+E+


Grids with walls on their cell edges have graphs like this:

1  
2  
3  
4  
5  
6  
7  
+E+E+E+E+ +E+E+E+E+E+
E E E E E E E E E E E
+E+E+ +E+ +E+ +E+E+E+
E E E E E E E E E E E
+E+E+ +E+ +E+ +E+E+E+
E E E E E E E E E E E
+E+E+ +E+E+E+ +E+E+E+


When adding nodes to the list you add the neighboring node
if(!grid.edgeBlocked(currentCell, aNeighbor) && !grid.isOccupied(aNeighbor))
instead of
if(!grid.isOccupied(aNeighbor))
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline sproket

Junior Member


Medals: 1



« Reply #3 - Posted 2013-01-28 23:32:42 »

OK thanks. Smiley  That means I just have normal bugs but I don't have to tweak the algorithm itself.

Offline Roquen
« Reply #4 - Posted 2013-01-28 23:38:57 »

Another common option is to have weights for cells..and unpassables have very high weights (just additive values).
Offline kulpae

Senior Newbie


Exp: 9 years



« Reply #5 - Posted 2013-01-29 00:17:36 »

The problem with high weights for impassable cells is that A* will take these cells if there is no other way to get in. e.g. if the target lies in an isolated area. If this behaviour isn't desired, then it's better to not include these impassable cells, as sproingie and Best Username Ever already said.
Offline Roquen
« Reply #6 - Posted 2013-01-29 00:47:27 »

Context dependent, but a very good point.  I was thinking in terms of weights related to movement cost, so it isn't possible (well...unless you support a god mode) in that case.  Of course there's the pruning issue as well.  Ignore me and move along.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (11 views)
2014-09-19 03:14:18

Dwinin (29 views)
2014-09-12 09:08:26

Norakomi (57 views)
2014-09-10 13:57:51

TehJavaDev (79 views)
2014-09-10 06:39:09

Tekkerue (40 views)
2014-09-09 02:24:56

mitcheeb (62 views)
2014-09-08 06:06:29

BurntPizza (45 views)
2014-09-07 01:13:42

Longarmx (30 views)
2014-09-07 01:12:14

Longarmx (36 views)
2014-09-07 01:11:22

Longarmx (36 views)
2014-09-07 01:10:19
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org 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‑gaming.org
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!