[PHP] Déterminer le prochain point d'une spirale carrée dans une grille

[Maz]

+1 Xenos. Pour moi la "non-récursivité" dans ce cas était évidente. J'ai retranscris le code de ma fonction en Ruby pour ceux que ça intéresses, je la posterais dans quelques jours.

[niahoo]

Les fonctions récursives sont plus simples à écrire et pour moi c'est ce qui importe le plus.
Ensuite, des calculs de spirale sur 10 000 points j'espère que tu ne le fais pas à chaque requête, donc optimiser à mort me semble moins important qu'un code simple et lisible.

Par contre, j'ai pas vraiment saisi pourquoi utiliser de l'objet induisait la récursivité. Le langage dans lequel j'utilise le plus la récursivité est erlang, où les objets n'existent pas dans la syntaxe.

[Xenos]

Oui, plus simples à écrire, mais dans certains cas, il vaut mieux passer 2 jours sur une fonction qui sera 100x plus rapide.
Imagine qu'il failles 3 secondes pour éxécuter la fonction récursive, et qu'on veuille executer cette fonction environ 100.000 fois (dans mon cas, ce n'est pas pour du php, mais pour un compilateur de map c++), soit, au total, 300.000 secondes d'éxecution (3,5 jours en gros). En y passant 2 jours pour tomber à 0.03s / execution (total: 3000 secondes, 1h), on est franchement gagnant.
De plus, dans mon cas, le compilateur sera lancé sur plusieurs ordinateurs (le programme s'éxécute en local: chaque utilisateur lance son instance), donc, si le programme dure N secondes et qu'il y a P utilisateurs, je vais faire perdre l'équivalent de N*P secondes aux utilisateurs, et cela commence à faire beaucoup quand le nombre d'utilisateur augmente!

Bref, je suis d'accord que, dans certains cas (peut-être le cas présent), un récursif suffit peut-être, mais disposer d'un non-récursif permet non seulement à ceux qui avaient le récursif d'avoir une autre piste, mais cela ouvre la porte à ceux qui avaient besoin d'un non-récursif. En gros, c'est que du bonus.

& +1, pourquoi l'objet impliquerait le récursif? A moins que tu n'ai, en tête, l'idée d'un objet = 1 point de spirale, et que la classe de cet objet dispose d'une méthode "creer_prochain_point()".

[niahoo]

Bon je viens de lire la doc et php n'est pas optimisé pour une récursion sur plus de 200 itérations donc en effet ça serait pas une bonne idée pour 10 000 points !

[Wells]

Pourait on s'en servir pour generer une galaxie de planete en spirale?

[Maz]

Oui, il est tout à fait possible de générer une galaxie de planète. Le seul "hic" est que la galaxie serais carrée ,)

[Xenos]

Une galaxie en spirale possède plusieurs branches courbes qui aprtent d'un point central, or, la présente spirale n'a qu'une seule branche partant de son centre... Une galaxie en spiral aurait plus la forme d'une croix gammée finalement, qui continuerait en s'enroulant sur elle-même

[Maz]

Oui, c'est sur qu'avec ce script ta galaxie en plus d'être carrée, elle n'aurait qu'une seule "branche". Ou alors en modifiant un peu, tu pourrais généré 4 branches. Maintenant je penses que c'est vraiment poussé le vice que de vouloir recréé à l'identique une galaxie proprement dite pour un jeu web. Et pourtant je suis du genre à vraiment peaufiner pour pas grand chose ,p

[Xenos]

Dans le cas présent, pour une spirale (qui est quand meme pas franchement matricielle, c'est à dire pas facile à caser dans une grille de carrés), il vaudrait mieux avoir des coordonnées X et Y à virgule, et non forcément entières. Là, ce sera possible de créer un algo qui placera la planète sur une branche de la spirale, avec plus de chances d'être proche du centre que d'en être éloigné.

[jo_link_noir]

(desole pour les accent, clavier qwerty :/)

Pourquoi vous tenez absolument à ne pas utiliser la récursivité, alors que ça semble très indiqué dans ce cas précis ?

Je pense qu'il vaut mieux le faire a coup d'iterateur, c'est plus fun a utiliser

L'algo que j'ai fait part d'une position aleatoire dans la map (par defaut le centre) et s'arrete a une position donne (par defaut un coin de la carte (depend de la direction de la spirale: droite, bas, gauche, haut))
C'est un complement des 2 autres ^^

<?php

class Rect

{

	private $width, $height;



	function __construct($width, $height = null){

		$this->width = $width;

		$this->height = $height ?: $width;

	}



	function width(){

		return $this->width;

	}



	function height(){

		return $this->height;

	}



	function size(){

		return $this->height * $this->width;

	}



	function origin(){

		return floor($this->height / 2) * $this->width + floor($this->width / 2);

	}



	function index($x,$y){

		return $x + $y * $this->width;

	}



	function coord($index){

		return array($index % $this->width, $index / $this->width);

	}

}



class Nexter

{

	private $add;



	function __construct($add = 1){

		$this->add = $add;

	}



	function per(&$n){

		$n += $this->add;

	}

}



class SpiralSquareIterator implements Iterator

{

	const TO_RIGHT = 0;

	const TO_DOWN = 1;

	const TO_LEFT = 2;

	const TO_UP = 3;



	private $begin, $it, $end, $circular, $step, $to, $m, $odd, $inner, $nexter;



	function __construct($shape, $begin = null, $end = null, $to = SpiralSquareIterator::TO_RIGHT){

		$this->begin = $begin === null ? $shape->origin() : $begin;

		$this->end = $end ?: self::getEndIndex($to, $shape);

		$h = $shape->height();

		//SplFixedArray ?

		$this->circular = new InfiniteIterator(new ArrayIterator(array(

			new Nexter(1),

			new Nexter($h),

			new Nexter(-1),

			new Nexter(-$h),

		)));

		$this->to = $to;

	}



	static function getEndIndex($to, $shape){

		return $to === SpiralSquareIterator::TO_RIGHT ? $shape->width() - 1 : (

			$to === SpiralSquareIterator::TO_DOWN ? $shape->size() - 1 : (

			$to === SpiralSquareIterator::TO_LEFT ? $shape->height() * ($shape->width() - 1) :

			0));

	}



	function rewind(){

		$this->it = $this->begin;

		$this->circular->rewind();

		for ($n = $this->to; $n--; $this->circular->next());

		$this->m = 1;

		$this->step = 0;

		$this->odd = false;

		$this->inner = false;

		$this->nexter = $this->circular->current();

	}



	function valid(){

		if ($this->inner)

			return false;

		if ($this->it == $this->end)

			$this->inner = true;

		return true;

	}



	function current(){

		return $this->it;

	}



	/**

	 * Retourne l'indice du bord du carré (↑:0, →:1, ↓:2, ←: 3)

	 * @attention la clef étant 0,1,2 ou 3 celle-ci n'est pas unique

	 */

	function key(){

		$r = $this->circular->key();

		return $r === $this->to && !$this->m

			? ($this->to + 1 === 4 ? 0 : $this->to + 1) : $r;

	}



	function next(){

		if (!$this->m--){

			$this->m = ($this->odd = !$this->odd) ? $this->step : ++$this->step;

			$this->circular->next();

			$this->nexter = $this->circular->current();

		}

		$this->nexter->per($this->it);

	}



	/**

	 * @param bool $get_pair = false : si true la valeur est une pair avec comme premier

	 *  indice la clef de l'itérateur

	 * @param bool $calculate_distance = true : si true l'itérateur sert de clef et la valeur

	 *  et la distance par rapport au centre de la spiral

	 *

	 * $get_pair = false & $calculate_distance = false : $r[] = $this->current()

	 * $get_pair = true & $calculate_distance = false : $r[] = array($this->key(), $this->current())

	 * $get_pair = false & $calculate_distance = true : $r[$this->current()] = $n++

	 * $get_pair = true & $calculate_distance = true: $r[$this->current()] = array($this->key(), $n++)

	 */

	function toArray($get_pair = false, $calculate_distance = true){

		$r = array();

		$this->rewind();

		if ($calculate_distance) {

			$n = 0;

			if ($get_pair){

				while ($this->it != $this->end){

					$r[$this->it] = array($this->key(), $n++);

					$this->next();

				}

				$r[$this->it] = array($this->key(), $n++);

			} else {

				while ($this->it != $this->end){

					$r[$this->it] = $n++;

					$this->next();

				}

				$r[$this->it] = $n++;

			}

		}

		else if ($get_pair){

			while ($this->it != $this->end){

				$r[] = array($this->key(), $this->it);

				$this->next();

			}

			$r[] = array($this->key(), $this->it);

		} else {

			while ($this->it != $this->end){

				$r[] = $this->it;

				$this->next();

			}

			$r[] = $this->it;

		}

		return $r;

	}

}



function spiral_square($shape, $begin = null, $end = null, $to = SpiralSquareIterator::TO_RIGHT,

				$get_pair = false, $calculate_distance = true)

{

	$it = new SpiralSquareIterator($shape, $begin, $end, $to);

	return $it->toArray($get_pair, $calculate_distance);

}



$square = new Rect(17);

$indices = spiral_square($square, null, null, SpiralSquareIterator::TO_RIGHT, true);

/*$indices = array();

$n = 0;

foreach(new SpiralSquareIterator($square) as $border => $i){

	$indices[$i] = array($border, $n++);

}*/



//var_dump(iterator_to_array(new SpiralSquareIterator($square), false));

//var_dump($indices);



$c = array('#00D', '#000', '#D00', '#0D0');



echo '<table border=1>';

for ($i = 0, $end = $square->size(); $i != $end; )

{

	echo '<tr>';

	for ($endx = $i + $square->width(); $i != $endx; ++$i)

	{

		echo isset($indices[$i])

			? '<td style="color:'.$c[$indices[$i][0]].'">'.$indices[$i][1].'</td>'

			: '<td style="color:darkorange">'.$i.'</td>';

	}

	echo '</tr>';

}

echo '</table>';