what is the most efficient greedy snake's automatic display algorithm?

[rabbit_dance]

http://img1.mydrivers.com/img/20140930/45c9b6261ccc4fe29332270f963d8832.gif

[Bart]

AS ALWAYS IT WILL INVOLVE WRITNG THE ENTIRE CODE IN CAPITALS AND USING NON-STANDARD INDENTATION.

Bart

[User137]

Draw white at the head and black when tail position changes. Don't need to clear screen and draw the whole snake every frame, if you're asking for the most efficient way. OpenGL or just Canvas for this, i don't think it would matter much.

[rabbit_dance]

Draw white at the head and black when tail position changes. Don't need to clear screen and draw the whole snake every frame, if you're asking for the most efficient way. OpenGL or just Canvas for this, i don't think it would matter much.

my question is the algorithm to let snake head's motion avoid the snake's body collision most efficiently.

[Leledumbo]

Ever taken an intelligent system class? Yes or no, I suggest you to (re)read chapters about searching. AI in games is just state space searching. The best one I know for general case is A*, but for certain games best-first might perform better. Both requires you to write good heuristic/evaluation function to determine which state is the best to take from current one, which certainly varies from one game to another.

[rabbit_dance]

AS ALWAYS IT WILL INVOLVE WRITNG THE ENTIRE CODE IN CAPITALS AND USING NON-STANDARD INDENTATION.

Bart

how should i write to revise NON-STANDARD INDENTATION to STANDARD INDENTATION?

[rabbit_dance]

AS ALWAYS IT WILL INVOLVE WRITNG THE ENTIRE CODE IN CAPITALS AND USING NON-STANDARD INDENTATION.

Bart

i dont want to shift capitals too often.

[rabbit_dance]

why does no one anwsered me so long?

[rabbit_dance]

i mean how to shift characters automatically

[User137]

You quoted troll post twice and what would you mean by shifting characters? Worm game mechanics are not programmed as strings, even if displayed on old DOS based box.

[Leledumbo]

why does no one anwsered me so long?

I did, but you don't do anything upon it.

[engkin]

This snake is impressive!!

A* would help the snake to find a path from its head to the apple without biting itself. With every movement a better path might open up, which could be discovered by repeating the search with A* or some similar algorithm.

IMHO, A* will not prevent the snake from trapping itself. It could reach to an apple in an area that does not have enough space for the snake to leave. Any idea how to prevent that?

If you watch this snake, you'll see that it does not go for the shortest path after the 20^th apple.

[Leledumbo]

IMHO, A* will not prevent the snake from trapping itself. It could reach to an apple in an area that does not have enough space for the snake to leave. Any idea how to prevent that?

A good heuristic function will prevent that by marking the states where the snake body lies as unpassable, I usually give -1 score to such state while maintaining all other states to be non-negative. That way, the path will never be chosen.

[engkin]

IMHO, A* will not prevent the snake from trapping itself. It could reach to an apple in an area that does not have enough space for the snake to leave. Any idea how to prevent that?

A good heuristic function will prevent that by marking the states where the snake body lies as unpassable, I usually give -1 score to such state while maintaining all other states to be non-negative. That way, the path will never be chosen.

I think I failed to explain properly. Here is my second try:
The first attached image shows how the white snake would move on the green path to eat the red apple. The second image shows how it trapped itself.

It did use A* and it did avoid biting itself by considering its own body not passable.

[BeniBela]

You can calculate a longest/Hamiltonian cycle. (NP-complete, but there are some trivial solutions for a grid)

The snake can cycle around that path endlessly and will only bite itself, when it covers every cell in the grid.

It will also visit every cell, so eventually it will get to the next .. apple.

Biggest problem is to find cycles that look nice