Java-Gaming.org 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
Pages: [1]
 ignore  |  Print
 Pathfinding distance algorithm  (Read 745 times) 0 Members and 1 Guest are viewing this topic.
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:

 1 `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:
 1 `Math.pow(Math.abs(startX-endX),2)+Math.pow(Math.abs(startY-endY),2)`

and Euclidean
 1 `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?
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:

...)->(1)->(2)->(3)->(...

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.

Quote
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.
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.
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 Packagingby philfrei2019-02-17 20:25:53Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20
 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