Forum PHP.pl

Witam czy ktoś wie w jaki sposób napisać algorytm mrówkowy dla grafu najkrótszej drogi miedzy miastem a i b z ominięciem przeszkód x, y , z? Jeśli tak to proszę o pomoc

Ten post edytował Landon 5.05.2008, 13:17:21

No tak nie powiedziałem o co chodzi więc tak (a i dzięki za ten link) ...

Operuje na układzie współrzędnych z ustawionymi przeszkodami które muszą zostać ominięte... mam podany punkt początkowy i końcowy. Moim zadaniem jest przejście przez najkrótszą drogę pomiędzy tymi punktami. Następnie wyliczenie długości trasy i średniej szybkości z danych przypisanych do współrzędnych

Nie wiem czy zauważyłeś http://www.google.pl/search?q=ant-cycle to link do google szukam tam lecz zbyt wiele nie mogę znaleźć

Po wielu trudach i zmaganiach zrozumiałem zasadę działania tego algorytmu no ale mam problem z zastosowaniem.

Mam tablicę 2 wymiarową

[PHP] pobierz, plaintext 
<?php
$tablica = array();
$tablica[0][0] = 0;
$tablica[0][1] = 'woda';
$tablica[0][2] = 'woda';
$tablica[0][3] = 'woda';
$tablica[0][4] = 'woda';
$tablica[0][5] = 'woda';
?>
[PHP] pobierz, plaintext 

itd...

muszę odpalić pętle do {} while aż do wykonania warunku
następnie puścić pierwszą mrówkę i zapisać jej pokonaną drogę do tablicy
no i zwiększyć w tablicy wartość o 1 $tablica[0][0] = 0;

i doszedłem do czegoś takiego:

[PHP] pobierz, plaintext 
<?
 
$tablica = array();
$tablica[0][0] = 1;
$tablica[1][0] = 'woda';
$tablica[2][0] = 'woda';
$tablica[3][0] = 'woda';
$tablica[4][0] = 'woda';
$tablica[5][0] = 'woda';
 
$tablica[0][1] = 1;
$tablica[1][1] = 1;
$tablica[2][1] = 1;
$tablica[3][1] = 1;
$tablica[4][1] = 'woda';
$tablica[5][1] = 'woda';
 
$tablica[0][2] = 1;
$tablica[1][2] = 1;
$tablica[2][2] = 1;
$tablica[3][2] = 1;
$tablica[4][2] = 'woda';
$tablica[5][2] = 'woda';
 
$tablica[0][3] = 1;
$tablica[1][3] = 1;
$tablica[2][3] = 1;
$tablica[3][3] = 1;
$tablica[4][3] = 'woda';
$tablica[5][3] = 'woda';
 
$tablica[0][4] = 1;
$tablica[1][4] = 'woda';
$tablica[2][4] = 'woda';
$tablica[3][4] = 1;
$tablica[4][4] = 'woda';
$tablica[5][4] = 'woda';
 
$tablica[0][5] = 1;
$tablica[1][5] = 1;
$tablica[2][5] = 1;
$tablica[3][5] = 1;
$tablica[4][5] = 'woda';
$tablica[5][5] = 'woda';
 
$tablica[0][6] = 'woda';
$tablica[1][6] = 'woda';
$tablica[2][6] = 'woda';
$tablica[3][6] = 1;
$tablica[4][6] = 'woda';
$tablica[5][6] = 'woda';
 
$tablica[0][7] = 'woda';
$tablica[1][7] = 'woda';
$tablica[2][7] = 'woda';
$tablica[3][7] = 1;
$tablica[4][7] = 'woda';
$tablica[5][7] = 'woda';
 
$tablica[0][8] = 'woda';
$tablica[1][8] = 'woda';
$tablica[2][8] = 'woda';
$tablica[3][8] = 1;
$tablica[4][8] = 'woda';
$tablica[5][8] = 'woda';
 
$tablica[0][9] = 1;
$tablica[1][9] = 1;
$tablica[2][9] = 1;
$tablica[3][9] = 1;
$tablica[4][9] = 'woda';
$tablica[5][9] = 'woda';
 
$start_x = 0;
$start_y = 0;
$stop_x = $_GET['x'];
$stop_y = $_GET['y'];
 
if ($tablica[$stop_x][$stop_y] == 'woda') {
  echo 'Wskazany punkt jest w wodzie<br />';
} else {
  $op = 0;
  $dlogosc = array();
  $i = 0;
  do {
	$o_x = $start_x;
	$o_y = $start_y;
	$tablica[$o_x][$o_y]++;
	$i++;
	$dlogosc[$i] = 1;
	do {
	  if ($o_x < $stop_x) $o_x++;
	  elseif ($o_x > $stop_x) $o_x--;
 
	  if ($o_y < $stop_y) $o_y++;
	  elseif ($o_y > $stop_y) $o_y--;
 
	  $tablica[$o_x][$o_y]++;
	  $dlogosc[$i]++;
	} while ($o_x != $stop_x || $o_y != $stop_y);
  } while ($op == 1);
  if ($stop_x == $start_x && $start_y == $stop_y) {
	echo 'Wskazane współrzędne są na poczatku<br />';
  } else {
	echo 'Długość '.$dlogosc[$i].' kratek<br />';
  }
}
 
echo '<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<table cellspacing="0" cellpadding="0">';
foreach ($tablica as $k => $w) {
  echo '<tr>';
  foreach ($w as $k2 => $w2) {
	echo '<td style="background-color:'.($w2 != 'woda' ? $w2 == 1 ? 'green' : 'red' : 'blue').'; 
		width: 50px; height: 50px;">&nbsp;</td>';
  }
  echo '</tr>';
}
echo '</table>';
?>
[PHP] pobierz, plaintext 

Powoli idę do przodu... (próbuje dopisać by mijał ale chyba funkcje muszę wprowadzić do tego)

http://rdzen.osadnicy.net/table.php?x=2&y=5

Ten post edytował Landon 11.06.2008, 12:51:05

Czy to nie jest klastyczny problem najkrótszej ścieżki ? Zobacz to: A*

Algorytm mrowkowy to NIE jest A*

Gdzie ja napisałem że jest ? Po prostu chciałem zasugerować autorowi tematu, że to typowy problem rozwiązywany przez algorytm A star, więc może łatwiej będzie o przykłady implementacji.

jeśli chodzi o A* to tu jest ciekawy link:

http://www.policyalmanac.org/games/aStarTutorial_pl.htm

muszę się przyjrzeć temu dokładniej

Mam teraz coś takiego:
http://test.osadnicy.net/astar/

teraz tylko zostało uprościć kod i przenieść do js

o całe 500ms przyśpieszony ale i tak zbyt wolno średnio wypada koło 150-200ms

Ten post edytował Landon 11.06.2008, 19:46:55