2

I have working A* algorithm, but I want to improve it. It finds the shortest path and everything appears as it should. The problem is that I want for route to keep distance (1 empty node or more) from non-walkable grid cells.

Any ideas how to solve this problem?

How it looks now:

enter image description here

What I want to do:

enter image description here

Improve this question
8
  • 1
    Why do the yellow dots not avoid the walls all the way along? Commented Mar 13, 2014 at 0:00
  • Sorry for not fully illustrated example. It should go till the end. Commented Mar 13, 2014 at 0:01
  • 3
    So how about this: when your A* algorithm needs to know whether a square is a wall, tell it that the square is a wall if the square has any wall neighbours. Commented Mar 13, 2014 at 0:05
  • The above would work until you had a gap with only 1 block width to get through, then it would assume that there is a wall there and no path could be found. Commented Mar 13, 2014 at 0:15
  • 1
    You could make your Dot think it is wider than it actually is (3x3 rather than 1x1), that would give basically give it padding, but may introduce collision detection problems with the walls. Commented Mar 13, 2014 at 0:17

1 Answer 1

Reset to default
1

Solution 1: Make your dot think it is bigger than it actually is (3x3 instead of 1x1) then work out path based on edges of the 3x3 square. (May require collision detection code, also a bypass to allow it through 1 block size gaps.)

Solution 2: Calculate path as normal with an additional check so move your block 1 space away from the wall if there is space to do so.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.