Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (804)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (868)
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  
  Astar pathfinding diagonal support  (Read 8923 times)
0 Members and 1 Guest are viewing this topic.
Offline SuperMario
« Posted 2015-02-10 15:38:39 »

http://prntscr.com/63emxa
this is what the path looks like
I want it to look like this http://prntscr.com/63eo9b
while keeping diagonals when there are no blocked tiles. like this http://prntscr.com/63eon5

Sorry for the vague description
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #1 - Posted 2015-02-10 16:24:41 »

if that means that you want tiles always to be connected by their sides - you might want to look into bresenham's line :

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

and continue with super-cover :

http://www.java-gaming.org/topics/another-line-grid-intersection/33755/msg/317598/view.html#msg317598

Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2015-02-10 16:30:31 »

Simply remove the edges you deem impassible: for every diagonal edge verify that it touches/intersects 4 empty cells.

basil_: bresenham seems an odd choice for his specific request (conditional diagonal edges) as it solves quite a few problems, but more or less would make his problem worse Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #3 - Posted 2015-02-10 16:55:06 »

yea, don't listen to me. i'm way off most time anyway Wink
Offline SuperMario
« Reply #4 - Posted 2015-02-10 17:33:33 »

I'll try that Riven  Grin
Offline SuperMario
« Reply #5 - Posted 2015-02-10 18:13:09 »

I'm struggling to do this :S
Would be very grateful if somebody could help me with it.

this code is used to check if its a solid tile.
1  
2  
3  
if (MapManager.isBlocked(x,y)) {
this tile is clipped
}


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
public Node[] getNeighbors(Node goal) {
      Node[] neighbors = new Node[8];
      int count = 0;
      for (int i = -1; i < 2; i++) {
         for (int j = -1; j < 2; j++) {
            if (i == 0 && j == 0)
               continue;
            Node node = new Node(x + i, y + j, this);
            node.cost = node.distance(this);
            node.heuristic = node.heuristic(goal);
            neighbors[count++] = node;

         }
      }
      return neighbors;
   }
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2015-02-10 18:17:20 »

if both i and h are not zero, you're dealing with a diagonal edge to a neighbour. in that case, check whether there is any blocked cell in the 3 cells the edge is pointing to. if so, don't add the node to the neighbour array.


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline SuperMario
« Reply #7 - Posted 2015-02-10 18:20:12 »

check whether there is any blocked cell in the 3 cells the edge is pointing to

How would I do this exactly?
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2015-02-10 18:21:59 »

the coords of the three cells:
(x+i, y+j)
(x+i, y)
(x, y+j)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline SuperMario
« Reply #9 - Posted 2015-02-10 18:29:02 »

http://prntscr.com/63gx9h

It's avoiding some tiles when not needed

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
public Node[] getNeighbors(Node goal) {
      Node[] neighbors = new Node[8];
      int count = 0;
      for (int i = -1; i < 2; i++) {
         for (int j = -1; j < 2; j++) {
            if (i == 0 && j == 0)
               continue;
            if (i != 0 && j != 0) {
               if (!MapManager.isWalkable(x + i, y + j)
                     || !MapManager.isWalkable(x + i, y)
                     || !MapManager.isWalkable(x, y + j)) {
                  System.out
                        .println("diagonal tile not touching 4 empty tiles");
                  break;
               }
            }
            Node node = new Node(x + i, y + j, this);
            node.cost = node.distance(this);
            node.heuristic = node.heuristic(goal);
            neighbors[count++] = node;
         }
      }
      return neighbors;
   }
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SuperMario
« Reply #10 - Posted 2015-02-10 19:19:02 »

should be walking across the green path, http://prntscr.com/63hpd3
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2015-02-10 19:31:25 »

change line 14 to: continue

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2015-02-10 19:37:16 »

to wrap it up, rename i to dx, j to dy, and change the conditions to: <= +1, instead of < 2, to add meaning to the code.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline SuperMario
« Reply #13 - Posted 2015-02-10 19:51:19 »

Yes! it's working thank you so much!
Pages: [1]
  ignore  |  Print  
 
 

 
Riven (579 views)
2019-09-04 15:33:17

hadezbladez (5501 views)
2018-11-16 13:46:03

hadezbladez (2398 views)
2018-11-16 13:41:33

hadezbladez (5761 views)
2018-11-16 13:35:35

hadezbladez (1220 views)
2018-11-16 13:32:03

EgonOlsen (4660 views)
2018-06-10 19:43:48

EgonOlsen (5681 views)
2018-06-10 19:43:44

EgonOlsen (3196 views)
2018-06-10 19:43:20

DesertCoockie (4094 views)
2018-05-13 18:23:11

nelsongames (5113 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04: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!