Алгоритъм за пътуване за пространство за непрекъснато търсене? - c #, алгоритъм, unity5, pathing

В момента правя RTS игра в единство и имам нужда от начин да изчислим най-краткия път между две точки на непрекъсната 2d равнина, където има някои препятствия.

Имам начална позиция, крайна позиция и aфункция, която може да тества дали дадена позиция е валидна. Имам нужда от алгоритъм, който връща поредица от точки, за да се движи, за да стигнем до целта.

Повечето алгоритми за маршрутизиране като A * и IDA *които знам, изискват дискретизирани пространства за търсене. Аз бих разделил самолета на решетка, но се страхувам, че това ще доведе до зигзагови модели, които изглеждат наистина неестествено, когато се движат по диагонала. Има ли начин да се облекчи този проблем или друг алгоритъм, който мога да използвам? Не е нужно дори да намери най-краткия път, а само пътя, който има смисъл.

Отговори:

Един от подходите може да бъде дискретизирането на търсенетопространството, като се вземат предвид само точките, които са интересни за рендосване - точките на границите на препятствията, например само ъглите на ограничителните кутии, и след това използвате някой от алгоритмите, които вече знаете.

Друга възможност е да се изчисли на мрежата и след това да се изглади най-добрият път, намерен в мрежата.