Да, структурите от данни биха ви помогнали много при този вид проблем. Ще се опитам да обясня как работи A* и след това ще дам по-добър псевдокод.
A* е най-добрият алгоритъм за търсене. Това означава, че трябва да отгатне кои опции са най-добри и първо да се опита да ги проучи. Това изисква да следите списък с опции, обикновено наричан „Отпред“ (както в предната линия). Той не следи път, намерен досега, както в текущия ви алгоритъм. Алгоритъмът работи на две фази...
Фаза 1
По принцип започвате от началната позиция S, а всички съседни позиции (север, запад, юг и изток) ще бъдат отпред. След това алгоритъмът намира най-обещаващата от опциите отпред (да я наречем P) и я разширява. Позицията P се премахва от предната част, но вместо това се добавят всички нейни съседи. Е, не всички негови съседи; само съседите, които са действителни опции за отиване. Не можем да влезем в кула и не бихме искали да се върнем на място, което сме виждали преди. От новия Фронт се избира най-обещаващият вариант и т.н. Когато най-обещаващата опция е целта C, алгоритъмът спира и влиза във фаза 2.
Обикновено най-обещаващият вариант би бил този, който е най-близо до целта по права линия (без да се обръща внимание на препятствията). Така че обикновено винаги първо ще изследва този, който е най-близо до целта. Това кара алгоритъма да върви към целта по нещо като права линия. Ако обаче тази линия е блокирана от някакво препятствие, позициите на препятствието не трябва да се добавят към предната част. Те не са жизнеспособни опции. Така че в следващия кръг тогава някоя друга позиция отпред ще бъде избрана като най-добра опция и търсенето продължава оттам. Така се излиза от задънени улици като тази във вашия пример. Разгледайте тази илюстрация, за да разберете какво имам предвид: https://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif Предната част е кухите сини точки и те маркират точки, където вече са били в сянка от червено до зелено, и непроходими места с плътни сини точки.
Във фаза 2 ще ни е необходима допълнителна информация, която да ни помогне да намерим най-краткия път обратно, когато намерихме целта. За тази цел ние съхраняваме във всяка позиция позицията, от която сме дошли. Ако алгоритъмът работи, позицията, от която идваме, задължително е по-близо до S от всеки друг съсед. Разгледайте псевдокода по-долу, ако не разбирате какво имам предвид.
Фаза 2
Когато замъкът C бъде намерен, следващата стъпка е да намерите пътя си обратно към началото, като съберете кой е най-добрият път. Във фаза 1 съхранихме позицията, от която дойдохме, във всяка позиция, която изследвахме. Знаем, че тази позиция винаги трябва да е по-близо до S (без да пренебрегваме препятствията). Следователно задачата във фаза 2 е много проста: следвайте пътя обратно до позицията, от която сме дошли, всеки път, и следете тези позиции в списък. В края ще имате списък, който формира най-краткия път от C до S. След това просто трябва да обърнете този списък и ще получите своя отговор.
Ще дам някакъв псевдокод, за да го обясня. Има много примери за реален код (също и в Java) в интернет. Този псевдокод предполага, че използвате 2D масив за представяне на мрежата. Алтернатива би била да имате обекти Node, което е по-лесно за разбиране в Pseudocode, но по-трудно за програмиране и подозирам, че все пак бихте използвали 2D масив.
//Phase 1
origins = new array[gridLength][gridWidth]; //Keeps track of 'where we came from'.
front = new Set(); //Empty set. You could use an array for this.
front.add(all neighbours of S);
while(true) { //This keeps on looping forever, unless it hits the "break" statement below.
best = findBestOption(front);
front.remove(best);
for(neighbour in (best's neighbours)) {
if(neighbour is not a tower and origins[neighbour x][neighbour y] == null) { //Not a tower, and not a position that we explored before.
front.add(neighbour);
origins[neighbour x][neighbour y] = best;
}
}
if(best == S) {
break; //Stops the loop. Ends phase 1.
}
}
//Phase 2
bestPath = new List(); //You should probably use Java's ArrayList class for this if you're allowed to do that. Otherwise select an array size that you know is large enough.
currentPosition = C; //Start at the endpoint.
bestPath.add(C);
while(currentPosition != S) { //Until we're back at the start.
currentPosition = origins[currentPosition.x][currentPosition.y];
bestPath.add(currentPosition);
}
bestPath.reverse();
И за метода findBestOption в този псевдокод:
findBestOption(front) {
bestPosition = null;
distanceOfBestPosition = Float.MAX_VALUE; //Some very high number to start with.
for(position in front) {
distance = Math.sqrt(position.x * position.x - C.x * C.x + position.y * position.y - C.y * C.y); //Euclidean distance (Pythagoras Theorem). This does the diagonal thing for you.
if(distance < distanceOfBestPosition) {
distanceOfBestPosition = distance;
bestPosition = position;
}
}
}
Надявам се това да помогне. Чувствайте се свободни да попитате!
person
Ghostkeeper
schedule
03.11.2013
