Please login or register.

Login with username, password and session length
Advanced search  

News:

This forum provides RSS feed. To query recent posts use this url. More...


Author Topic: A* pathfinding  (Read 6627 times)

0 Members and 1 Guest are viewing this topic.

mylesblasonato

  • Developer
  • Frequent poster
  • ****
  • Karma: 0
  • Offline Offline
  • Gender: Male
  • Posts: 265
  • "Give up is to fail as sacrifice is to succeed"
    • View Profile
    • Royal Wins
A* pathfinding
« on: September 13, 2010, 04:17:45 AM »

Hi guys :)
This question is for Mnemonic.

I am making my own adventure game engine and I want to implement pathfinding but I'm not sure how to go about it.
I understand how A* works but the algorithm uses a grid of nodes. How do I tell it to use the nodes only when the user clicks somewhere where an obstacle is in the way.

Hope that makes sense.
Cheers  ::beer
Myles Blasonato.
Logged
Lead Game Designer, Royal Wins.
@mylesblasonato
@royalwins
http://au.linkedin.com/pub/myles-blasonato/26/600/a38

Mnemonic

  • WME developer
  • Administrator
  • Addicted to WME forum
  • *
  • Karma: 41
  • Offline Offline
  • Gender: Male
  • Posts: 5683
    • View Profile
    • Dead:Code Site
Re: A* pathfinding
« Reply #1 on: September 13, 2010, 07:29:12 AM »

The question is, why would you do that? The point of pathfinding algorithm is to find the path no matter if there are obstacles or not.
Logged
Yes, I do have a twitter account
Please don't send me technical questions in private messages, use the forum. ::wave

mylesblasonato

  • Developer
  • Frequent poster
  • ****
  • Karma: 0
  • Offline Offline
  • Gender: Male
  • Posts: 265
  • "Give up is to fail as sacrifice is to succeed"
    • View Profile
    • Royal Wins
Re: A* pathfinding
« Reply #2 on: September 14, 2010, 02:59:00 AM »

In an RTS your statement would make sense but in an Adventure game their is no grid to use as nodes so waypoints are used instead and waypoints are the path.
In essence in an adventure game the path is already defined I just want my player to follow it. When do i make him follow it?

Cheers  ::beer
Myles Blasonato.
Logged
Lead Game Designer, Royal Wins.
@mylesblasonato
@royalwins
http://au.linkedin.com/pub/myles-blasonato/26/600/a38

Mnemonic

  • WME developer
  • Administrator
  • Addicted to WME forum
  • *
  • Karma: 41
  • Offline Offline
  • Gender: Male
  • Posts: 5683
    • View Profile
    • Dead:Code Site
Re: A* pathfinding
« Reply #3 on: September 15, 2010, 02:34:48 PM »

I think I still don't understand the question. Waypoints are nodes, but not every waypoint is accessible from all other waypoints. And their distances are different. So the goal of A* is to find those waypoints that form an ideal path from point A to point B. The path is not known, it needs to be found.
Logged
Yes, I do have a twitter account
Please don't send me technical questions in private messages, use the forum. ::wave

metamorphium

  • Global Moderator
  • Addicted to WME forum
  • *
  • Karma: 12
  • Offline Offline
  • Gender: Male
  • Posts: 1511
  • Vampires!
    • View Profile
    • CBE  software s.r.o.
Re: A* pathfinding
« Reply #4 on: September 15, 2010, 03:18:36 PM »

mylesb, I am not sure you actually understand how A* works. Can you try to elaborate what's your understanding of the algorithm. You can use A* on any level of map infrasctructure being it connecting towns and streets or simple grid. The form of the "map" doesn't matter. You simply find the fastest (understand most cost-efficient) route. In your case the map is constructed out of waypoints with first one being added as player's position and the last one is the target desired place. If your target is not directly visible, you use the A* to traverse through nodes to get the fastest route. A* would provide you with best route to the destination via waypoints (finding waypoint which has direct visibility of the target point). That's all it does. Difference in between dijkstra and A* is that while dijkstra blindly tries all ways until it finds the best, A* includes heuristical function trying to get the result faster by trying to move somewhat in the target direction first before trying other ways.
Logged
J.U.L.I.A. Enhanced Edition, Vampires!, J.U.L.I.A., J.U.L.I.A. Untold, Ghost in the Sheet

mylesblasonato

  • Developer
  • Frequent poster
  • ****
  • Karma: 0
  • Offline Offline
  • Gender: Male
  • Posts: 265
  • "Give up is to fail as sacrifice is to succeed"
    • View Profile
    • Royal Wins
Re: A* pathfinding
« Reply #5 on: September 16, 2010, 07:19:52 AM »

Hey guys,
So I totally get it now :P
I hate when sometimes it takes a while for stuff to sink in :)
Ok so now I know that A* finds the quickest from the start position to the end position.
It does this by using the nodes we place on the map.

It's totally working now.
Cheers  ::beer
Myles Blasonato
« Last Edit: September 16, 2010, 09:20:39 AM by mylesb »
Logged
Lead Game Designer, Royal Wins.
@mylesblasonato
@royalwins
http://au.linkedin.com/pub/myles-blasonato/26/600/a38
 

Page created in 0.04 seconds with 20 queries.