Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


About to implement A*, have some questions and need tips :)


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.

  • This topic is locked This topic is locked
3 replies to this topic

#1 crovea   Members   -  Reputation: 124

Like
0Likes
Like

Posted 21 July 2012 - 07:06 AM

Hey! I'm in the process of creating a game engine (who isn't, amirite) for top-down sprite 2d games with alot of units. (such as moba's and RTS games, diablo and scbw was made this way more or less).

So one of the last things i need in my physics subsystem/subengine is pathfinding, where i plan to use the A* algorithm which requires a grid(?).

I plan on using a tilemap for static obstacles (some kind of map loaded from a picture, showing which parts of the map are walkable, possibly using a quadtree)
And my already existing collision detection grid for semi dynamic obstacles (such as buildings, trees, craters, etc)

As mentioned, I use a variable size grid for collision detection. I initialize the grid field size to a size that is atleast the size of the largest units collision box.

Q: Which leads me to my first question, wouldn't this kind of grid be too big to also use for pathfinding? (maps will be much larger than a screen)

Q: Also with the size of the grid fields being variable from game to game, wouldn't that result in different and sometimes bad behavior?


1. Option would be to split the grid i already have into smaller fields.

Q: But with dynamic size grids, how would i go about partitioning it?

Alternatively, if the existing grid isn't usable i see two other options:

2. Create a new grid for pathfinding with fields always of the same size. (a pretty decent chunk of memory would be required)

3. Try an approach where i dynamically build fields/nodes based on coordinates. The objects could be pulled from a pool to improve performance.

Q: Is option 2 actually feasable? or am i missing something essential from A* that makes it unreasonable.
Q: Would option 1 actually be worthwhile despite the memory cost, due to being easier/simpler/faster?


Any advice, tips or experiences are welcomed Posted Image

Sponsor:

#2 Postie   Members   -  Reputation: 1039

Like
0Likes
Like

Posted 21 July 2012 - 06:46 PM

I'd recommend checking out the AI forum, as the A* algorithm is discussed there all the time.
Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#3 crovea   Members   -  Reputation: 124

Like
0Likes
Like

Posted 22 July 2012 - 03:40 AM

Thanks didn't realize it belonged there, i reposted now, assume thats alright!

Edited by crovea, 22 July 2012 - 03:41 AM.


#4 JTippetts   Moderators   -  Reputation: 8570

Like
0Likes
Like

Posted 22 July 2012 - 09:31 AM

Since you want it in AI, I'll close this one. The new one is here.




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