Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


2D Pathfinding


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 Plutonium   Members   -  Reputation: 349

Like
0Likes
Like

Posted 02 April 2013 - 01:12 PM

Hello, as allways doing some feature to my "game engine", and now I need info about path finding. Maybe anybody could give some advice what to read smile.png

What I want I painted, so would be easier to explain. There is pictures https://www.dropbox.com/sh/3apm1hupb12xdu4/jGuutop3aB

 

I need that my object go from one point to another.  As in first picture, if there is no blocks in path, so go simple straight line. Only begin and end points. As in second, if there would be block in path, find fastest way to walk around it. Now would be three point: begin, block corner and end points. If there would be more blocks - so more points would be too. 

My game is will be tile based. Now all object is 32x32 (tiles, enemies and so on), but what I thinking, is to make tiles 4x4, and all object would be same proportion as it (4x4, 8x8, 16x16, 32x32 ...) so one object could be on more then one tile. But it's just thinking for now

 

And sorry for english, really hard to remember to write good smile.png


Edited by Plutonium, 02 April 2013 - 01:12 PM.


Sponsor:

#2 Paradigm Shifter   Crossbones+   -  Reputation: 5410

Like
1Likes
Like

Posted 02 April 2013 - 01:14 PM

Can't see your picture...

 

You want to look at the A* algorithm for tile based (or node based) pathfinding http://en.wikipedia.org/wiki/A*_search_algorithm

 

which is usually more efficient than Djikstra's algorithm which is basically just a flood fill.

 

EDIT: I can see your picture now, can't see any tiles though ;)


Edited by Paradigm Shifter, 02 April 2013 - 01:18 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#3 Plutonium   Members   -  Reputation: 349

Like
0Likes
Like

Posted 02 April 2013 - 01:22 PM

Can't see your picture...

 

You want to look at the A* algorithm for tile based (or node based) pathfinding http://en.wikipedia.org/wiki/A*_search_algorithm

 

which is usually more efficient than Djikstra's algorithm which is basically just a flood fill.

 

EDIT: I can see your picture now, can't see any tiles though ;)

think that all rectangles are tiles (could be more then one in same place) and all other is alot of white rectangles :D that was just fast drawing :) 

But maybe not tiled based game would be better? Talking about pathfinding



#4 Paradigm Shifter   Crossbones+   -  Reputation: 5410

Like
0Likes
Like

Posted 02 April 2013 - 01:26 PM

Well check out A* anyway... or try doing it with Dijkstra's algorithm first which is easier to understand.

 

A* and Dijkstra's algorithm depend on nodes (which would be tile midpoints in a tile based game) existing on the map. (If you don't have tiles you need to subdivide your space into regions and place a node in each one, like a waypoint system).

 

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#5 ultramailman   Prime Members   -  Reputation: 1582

Like
0Likes
Like

Posted 02 April 2013 - 02:53 PM

But maybe not tiled based game would be better?

Your game map doesn't have to be tiled. If you can make a graph that represents your map, then you can use A* or Dijkstra's.



#6 KnolanCross   Members   -  Reputation: 1334

Like
0Likes
Like

Posted 02 April 2013 - 04:12 PM

If you use grids to store you world, you can use my A* implementation (it is implemented on C), you can find it (and how to use it) on my blog (link is on my signature).

 

The best resource I found was this one:

http://www.policyalmanac.org/games/aStarTutorial.htm


Edited by KnolanCross, 02 April 2013 - 04:18 PM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS