1

Im wondering if I can optimize my pathfinding code a bit, lets look at this map:

+ - wall, . - free, S - start, F - finish .S............. ............... ..........+++.. ..........+F+.. ..........+++.. ...............

The human will look at it and say its impossible, becouse finish is surrounded... But A-star MUST check all fields to ascertain, that there isnt possible road. Well, its not a problem with small maps. But when I have 256x265 map, it takes a lot of time to check all points. I think that i can stop searching while there are closed nodes arround the finish, i mean:

+ - wall, . - free, S - start, F - finish, X - closed node .S............. .........XXXXX. .........X+++X. .........X+F+X. .........X+++X. .........XXXXX.

And I want to finish in this situation (There is no entrance to "room" with finish). I thought to check h, and while none of open nodes is getting closer, then to finish... But im not sure if its ok, maybe there is any better way?

Thanx for any replies.

Improve this question

2 Answers 2

Reset to default
2

First of all this problem is better solved with breadth-first search, but I will assume you have a good reason to use a-star instead. However I still recommend you first check the connectivity between S and F with some kind of search(Breadth-first or depth-first search). This will solve our issue.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

so you mean I have to check if there is ANY road between S and F and then search for shortest?
In fact BFS will find the shortest road anyway. If you choose DFS you will just check if there is any road, yes.
I havent heard anything about BFS and DFS, I choose A*, becouse I heard its fast on big maps. Will it be faster to use DFS and then A*, or just BFS?
The best solution of this problem is using BFS and it will be as fast as possible.
Well, Its too hard for me. Im just 15... It was hard to implement A*, but I dont understand BFS and DFS at all. I think I gonna find a way to check if F isnt in closed "room". Anyway, great thanks for your help.
|
2

Assuming the map doesn't change, you can preprocess it by dividing it to connected components. It can be done with a fast disjoint set data structure. Then before launching A* you check in constant time that the source and destination belong to the same component. If not—no path exists, otherwie you run A* to find the path.

The downside is that you will need additional n-bits per cell where n = ceil(log C) for C being the number of connected components. If you have enough memory and can afford it then it's OK.

Edit: in case you fix n being small (e.g. one byte) and have more than that number of components (e.g. more than 256 for 8-bit n) then you can assign the same number to multiple components. To achieve best results make sure each component-id has nearly the same number of cells assigned to it.

Improve this answer

6 Comments

But in order to compute the connected components you need to run a search(for instance BFS) and once you've ran BFS you already have the answer - I see no reason why you would use A*.
@izomorphius: It's a reprocessing step (done just once for the whole map).
Ahh you mean for multiple queries. In that case yes, this will speed up the things.
O.o I dont understand at all. I just need to add that the map will change during game... But then I can just merge the tow cell sets...
@ybungalobill How can I connect/extend sets when something changes value?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.