Trémaux's Algorithm

Generator98

Hello community,

I am currently working on Scratch project to solve mazes. To solve them I am planning to use the Trémaux's Algorithm. I know there are other algorithms which are easier to code, but I already coded them in Scratch like the Wall Follower or the Pledge Algorithm. Problem with this Algorithm is that it is not memory Free and I dont know how to code it.

I am not asking for the perfect solution, just for help like how to start or how to think.

Thank you for your help
Kind regards,
Generator98

gdpr533f604550b2f20900645890

What do you mean by “memory free?”

I looked up the algorithm on Wikipedia. You'll want to start by defining a data structure to represent the paths.

Blaze349

Generator98 wrote:
Hello community,

I am currently working on Scratch project to solve mazes. To solve them I am planning to use the Trémaux's Algorithm. I know there are other algorithms which are easier to code, but I already coded them in Scratch like the Wall Follower or the Pledge Algorithm. Problem with this Algorithm is that it is not memory Free and I dont know how to code it.

I am not asking for the perfect solution, just for help like how to start or how to think.

Thank you for your help
Kind regards,
Generator98

I would use a list of nodes tor represent the maze. Each node would have a number representing how many times it has been marked and a list of addresses to the other paths.

Generator98

I would use a list of nodes tor represent the maze. Each node would have a number representing how many times it has been marked and a list of addresses to the other paths.

Thank you for your help! I understand how to make a list for nodes but I dont understand the thing with the adresses and the number of visits.

Generator98

Blaze349 wrote:
Generator98 wrote:
I would use a list of nodes tor represent the maze. Each node would have a number representing how many times it has been marked and a list of addresses to the other paths.

Thank you for your help! I understand how to make a list for nodes but I dont understand the thing with the adresses and the number of visits.

Last edited by Generator98 (July 26, 2017 13:00:39)

Blaze349

Generator98 wrote:

I would use a list of nodes tor represent the maze. Each node would have a number representing how many times it has been marked and a list of addresses to the other paths.

Thank you for your help! I understand how to make a list for nodes but I dont understand the thing with the adresses and the number of visits.

An address is simply a value that points to where the other path is in the list.

Generator98

Blaze349 wrote:

I would use a list of nodes tor represent the maze. Each node would have a number representing how many times it has been marked and a list of addresses to the other paths.

An address is simply a value that points to where the other path is in the list.

Thanks but how is it possible to represent the whole maze as a sumber of nodes? I mean the figure, the spirte doesnt know where the other nodes are. The figure only know what in front of him is.

Last edited by Generator98 (July 26, 2017 14:05:16)

Blaze349

Generator98 wrote:
Blaze349 wrote:
I would use a list of nodes tor represent the maze. Each node would have a number representing how many times it has been marked and a list of addresses to the other paths.

An address is simply a value that points to where the other path is in the list.

Thanks but how is it possible to represent the whole maze as a sumber of nodes? I mean the figure, the spirte doesnt know where the other nodes are. The figure only know what in front of him is.
You use a linked list.

gtoal

if it is a 2D grid maze, use an array. If it is a bunch of disjoint locations randomly connected, use linked lists.

Discuss Scratch