Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (781)
Games in Android Showcase (233)
games submitted by our members
Games in WIP (857)
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  
  Pathfinding distance algorithm  (Read 745 times)
0 Members and 1 Guest are viewing this topic.
Offline mudlee

Junior Devvie

Medals: 6
Exp: 5 years

« Posted 2018-09-27 11:43:35 »

Hi. I implemented a pathfinding solution with gdx-ai in my tile basede game, and I used Manhattan distance formula in estimation:

Math.abs(startX - endX) + Math.abs(startY - endY)

If the shortest path from point A to point B is diagonal, it's OK for ground units, the movement a little bit like zigzag, but it's OK.

I was thinking if there is a better solution to avoid that zigzag behavior to get a smooth movement, like in starcraft2. I tried pythagorean:

and Euclidean
Math.sqrt(Math.pow(Math.abs(endX-startX),2) + Math.pow(Math.abs(endY-startY),2))

but both resulted me a similar result.

So if the map looks like this:
01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16
and the point A is at 13, point B is at 04, than those takes a path like: 13->14->10->11->07->08->04 instead of 13->10->07->04

Any idea how can I achieve this?

UPDATE: is that a good idea to add the diagonal nodes to the node's connections?
Offline VaTTeRGeR
« Reply #1 - Posted 2018-09-27 16:20:11 »

You need to post-process the generated path. You can probably remove 90% of the nodes that make up your path.

Let's say you have these three nodes somewhere in your path:


If there is direct line of sight between node 1 and node 3 you can skip/remove node 2. Then do the same check for the next pair of nodes. If you do multiple of these reduction passes you'll end up with a pretty good path. For me the sweet spot was around 10 times (for every second node of the path, not just 10 removals but 10 full passes), which is still very cheap compared to the pathfinding itself and produces good results.

This will already remove 90% of the zig-zagginess, it won't be perfect but much better then the raw path.

UPDATE: is that a good idea to add the diagonal nodes to the node's connections?
Just try it, it'll make your path more accurate.
Offline mudlee

Junior Devvie

Medals: 6
Exp: 5 years

« Reply #2 - Posted 2018-09-28 03:30:31 »

Tried to connect diagonal nodes, it looks totally OK now, zigzag effect went away.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline codyorr5

Senior Newbie

Medals: 1

« Reply #3 - Posted 2019-02-09 01:28:41 »

Just google some tutorials on the " A* - algorithm ", its pretty neat for beginners to learn how pathfinding works
Pages: [1]
  ignore  |  Print  

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

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

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

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

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

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

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

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

nelsongames (2123 views)
2018-04-24 18:15:36

nelsongames (2817 views)
2018-04-24 18:14:32
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

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20 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!