Skip to main content
Game Development

Return to Question

added 1 character in body; edited tags
Source Link
MAnd
MAnd
  • 4.9k
  • 3
  • 23
  • 42

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* pathfindingpath-finding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 nodes, meaning that if the end node is blocked from passage, it would take about 2 seconds for it to realize this (A* without optimizations returns failed when the open list is empty, when it has inspected every path and realized there was no solution). And I want at least 20 fps!

I have not used any optimizations, and each point in the grid is a boolean blocked or unblocked. Any ways to speed it up?

For example, in Dota 2 (a popular MOBA), the map is full of trees and cliffs, and is 15,000 game units by 15,000 game units big, but the character starts moving as soon as you click where you want it to go. How do they do that, and is it a simple thing I am missing?

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* pathfinding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 nodes, meaning that if the end node is blocked from passage, it would take about 2 seconds for it to realize this (A* without optimizations returns failed when the open list is empty, when it has inspected every path and realized there was no solution). And I want at least 20 fps!

I have not used any optimizations, and each point in the grid is a boolean blocked or unblocked. Any ways to speed it up?

For example, in Dota 2 (a popular MOBA), the map is full of trees and cliffs, and is 15,000 game units by 15,000 game units big, but the character starts moving as soon as you click where you want it to go. How do they do that, and is it a simple thing I am missing?

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* path-finding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 nodes, meaning that if the end node is blocked from passage, it would take about 2 seconds for it to realize this (A* without optimizations returns failed when the open list is empty, when it has inspected every path and realized there was no solution). And I want at least 20 fps!

I have not used any optimizations, and each point in the grid is a boolean blocked or unblocked. Any ways to speed it up?

For example, in Dota 2 (a popular MOBA), the map is full of trees and cliffs, and is 15,000 game units by 15,000 game units big, but the character starts moving as soon as you click where you want it to go. How do they do that, and is it a simple thing I am missing?

Source Link
Demandooda
Demandooda
  • 125
  • 3
  • 13

A* pathfinding takes too long, shortcuts needed

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* pathfinding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 nodes, meaning that if the end node is blocked from passage, it would take about 2 seconds for it to realize this (A* without optimizations returns failed when the open list is empty, when it has inspected every path and realized there was no solution). And I want at least 20 fps!

I have not used any optimizations, and each point in the grid is a boolean blocked or unblocked. Any ways to speed it up?

For example, in Dota 2 (a popular MOBA), the map is full of trees and cliffs, and is 15,000 game units by 15,000 game units big, but the character starts moving as soon as you click where you want it to go. How do they do that, and is it a simple thing I am missing?