Toster Napisano Wrzesień 22, 2011 Zgłoś Share Napisano Wrzesień 22, 2011 Jakoś tak wyszło że musiałem sobie sportować Szukacza drogi z RuneSingera na Jave. Jakby ktoś szukał gotowej implementacji to nie krępować się: /* * AStar.java * Date: 2011-09-21 10:10:45 * Author: Bartłomiej Żarnowski * */ package pl.thetosters.generalzorg.pathfinder.astar; import java.awt.Point; import java.util.ArrayList; /** * @author Bartłomiej Żarnowski * @version 1.0.0 */ public class AStar { WayNode oList, cList, fList; SearchableMap theMap; public AStar(SearchableMap map){ theMap = map; WayNode tt; //tyle nodow do szukania drogi na maxa fList = new WayNode(); tt = fList; for(int t = 1; t < 1000; t++){ tt.next = new WayNode(); tt = tt.next; } } public ArrayList<Point> findWay(int sx, int sy, int ex, int ey){ cleanUp(oList); cleanUp(cList); WayNode temp, t, t2, tt; int cy; oList.uid = -1; cList.uid = -1; temp = fList; fList = fList.next; temp.x = sx; temp.y = sy; temp.uid = (sx << 16) | sy; temp.next = null; oList.next = temp; do{ //bierzemy pierwszy z gory if (oList.next == null) { break; } cy = 1000000; t = oList.next; tt = oList; t2 = tt; do{ if (t.cost < cy) { cy = t.cost; temp = t; t2 = tt; } tt = t; t = t.next; } while (t != null); t2.next = temp.next; temp.next = cList.next; cList.next = temp; //dokonujemy analizy elementow przyleglych AnalyzePosition(temp,-1,-1,ex,ey); AnalyzePosition(temp, 0,-1,ex,ey); AnalyzePosition(temp, 1,-1,ex,ey); AnalyzePosition(temp, 1, 0,ex,ey); AnalyzePosition(temp, 1, 1,ex,ey); AnalyzePosition(temp, 0, 1,ex,ey); AnalyzePosition(temp,-1, 1,ex,ey); AnalyzePosition(temp,-1, 0,ex,ey); } while (((temp.x == ex) && (temp.y == ey)) == false); //szukanie od tylca ArrayList<Point> arr = new ArrayList<Point>(); cy = 0; arr.add( new Point(temp.x, temp.y) ); do{ temp = temp.parent; arr.add( new Point(temp.x, temp.y) ); }while ( ( (temp.x == sx) && (temp.y == sy) ) == false); return arr; } /** * @param temp * @param i * @param j * @param ex * @param ey */ private void AnalyzePosition(WayNode node, int dx, int dy, int endx, int endy) { WayNode temp; int cx, cy, t; cx = node.x + dx; cy = node.y + dy; if ( (cx <0) || (cy < 0) || (cx >= theMap.Width()) || (cy >= theMap.Height()) ) { return; } if ( theMap.isObstacle(cx,cy) == true) { return; } //sprawdzamy czy nie mamy takiego noda w ktorejs z list ? t = (cx << 16) | cy; // <>false jest szybsze niz =true if ((onList(oList,t) != false) || (onList(cList,t) != false)) { return; } // temp := TWayNode.Create(cx, cy); //pobieramy z freeList zamiast tworzyc temp = fList; fList = fList.next; temp.x = cx; temp.y = cy; temp.uid = t; temp.parent = node; cx -= endx; if (cx < 0) { cx = -cx; } cy -= endy; if (cy < 0) { cy = -cy; } temp.cost = (cx+cy) << 4; //heuristic temp.next = oList.next; oList.next = temp; } /** * @param oList2 * @param t * @return */ private boolean onList(WayNode list, int i) { WayNode t; t = list; do { if (t.uid == i) { return true; } t = t.next; } while ( t != null); return false; } private void cleanUp(WayNode list){ WayNode t, t2; if (list.next == null){ return; } t = list.next; do { t2 = t.next; t.next = fList.next; fList.next = t; t = t2; } while (t != null); } } /* * SearchableMap.java * Date: 2011-09-21 10:19:12 * Author: Bartłomiej Żarnowski * */ package pl.thetosters.generalzorg.pathfinder.astar; /** * TODO: Opis * @author Bartłomiej Żarnowski * @version 1.0.0 */ public interface SearchableMap { /** * @return */ int Height(); /** * @return */ int Width(); /** * @param cx * @param cy * @return */ boolean isObstacle(int cx, int cy); } /* * Node.java * Date: 2011-09-21 10:17:28 * Author: Bartłomiej Żarnowski * */ package pl.thetosters.generalzorg.pathfinder.astar; /** * @author Bartłomiej Żarnowski * @version 1.0.0 */ public class WayNode { public WayNode parent; public WayNode next; public int cost; public int x, y; public int uid; } Always Dark<br /> Link do komentarza Udostępnij na innych stronach More sharing options...
Polecane posty
Zarchiwizowany
Ten temat jest archiwizowany i nie można dodawać nowych odpowiedzi.