Cześć, chciałbym zrobić grę w tym stylu:
http://www.pasjans.org/kulki/
Potrzebuję nazwy algorytmu albo jakiegoś opisu, w jaki sposób wybierana jest trasa, którą porusza się wybrana przez nas kulka. Zawsze jest wybierana najkrótsza ścieżka, o ile dojście do danego pola jest możliwe. Będą konieczne operacje na grafach? Pola będę przechowywać w tablicy dwuwymiarowej, będą oznaczane liczbami całkowitymi.
0
0
Zapewne jakiś Dijkstra i tak, grafy będą potrzebne.
0
Dijkstra wystarczy do tego problemu? To by było chyba zbyt banalne.
0
Nie mam pojęcia na czym polega ta gra, a nie raczyłeś tego opisać. Odpowiedziałem tylko na pytanie w jaki sposób wyznacza się najkrótszą ścieżkę w labiryncie - takie było pytanie postawione w temacie.
0
Do takich planszy stosuje sie algorytm A*
http://www.policyalmanac.org/games/aStarTutorial_pl.htm
0
@xxx_xx_x z armaty do muchy. A* to jest bardziej skomplikowany Dijkstra, a skoro autorowi nie zależy na kosmicznej wydajności to nie przesadzałbym tutaj :) Pewnie nawet Bellman-Ford by się nadał, a implementacja byłaby w 5 linijkach ;]
0
Dzięki za zainteresowanie. Przepraszam, że nie opisałem problemu. Sądziłem, że link Wam wystarczy. :) Nie zależy mi na wydajności. Aplikacja będzie napisana w c# i siatka nie będzie mieć więcej niż 10x10. Macie jakieś sugestie co do przechowywania tych pól i jakiejś implementacji grafu? Kulki różnych kolorów mógłbym przechowywac jako różne liczby całkowite, np. z przedziału <1,10>, 0 oznaczałoby miejsce wolne.
0
Najprościej? Użyj biblioteki która implementuje Dijkstre i buduj graf w reprezentacji jaką przyjmuje ta biblioteka ;]
0
Znalazłem bibliotekę, a dokładnie klasę, napisaną przez jakiegoś sympatyka c#. Algorytm śmiga idealnie, podpiąłem pod niego storyboardy i mam to, co chciałem, czyli dobrą bazę pod tworzenie różnych gierek logicznych z kulkami. Jakby ktoś był zainteresowany, to tutaj link do źródła: http://novciu.pl/wyszukiwanie-najkrotszej-drogi-algorytm-dijkstry-3/
0
Ja bym sie na ty arcie nie wzorował biorąc pod uwagę końcówkę, gdzie autor twierdzi że algorytm Prima rozwiązuje ten sam problem co algorytm Dijsktry i że jest jego modyfikacją ;] To jakis ultra wtf ;]