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?