﻿ A* pathfinding
• April 18, 2024, 09:40:11 AM
• Welcome, Guest

### News:

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

Pages: [1]

### AuthorTopic: A* pathfinding  (Read 6627 times)

0 Members and 1 Guest are viewing this topic.

#### mylesblasonato

• Developer
• Frequent poster
• Karma: 0
• Offline
• Gender:
• Posts: 265
• "Give up is to fail as sacrifice is to succeed"
##### 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
Myles Blasonato.
Logged
@mylesblasonato
@royalwins

#### Mnemonic

• WME developer
• Karma: 41
• Offline
• Gender:
• Posts: 5683
##### 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.

#### mylesblasonato

• Developer
• Frequent poster
• Karma: 0
• Offline
• Gender:
• Posts: 265
• "Give up is to fail as sacrifice is to succeed"
##### 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
Myles Blasonato.
Logged
@mylesblasonato
@royalwins

#### Mnemonic

• WME developer
• Karma: 41
• Offline
• Gender:
• Posts: 5683
##### 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.

#### metamorphium

• Global Moderator
• Karma: 12
• Offline
• Gender:
• Posts: 1511
• Vampires!
##### 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
• Gender:
• Posts: 265
• "Give up is to fail as sacrifice is to succeed"
##### Re: A* pathfinding
« Reply #5 on: September 16, 2010, 07:19:52 AM »

Hey guys,
So I totally get it now
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
Myles Blasonato
« Last Edit: September 16, 2010, 09:20:39 AM by mylesb »
Logged