Code for most of the automation

[Anonimi Angels]

So i created a repo of code i use on The Farmer Was Replaced,
if you have some suggestions to optimize the code feel free to make a pull request ill review it

https://github.com/AnonimiAngels/the_farmer_was_replaced/tree/master

[owenz]

The maze code I wrote just does it willy nilly and solves on average of < 3 secs, this is w/o any direction after the solve. What is your maze solver clocking it at for each iteration?

So 300 iterations my craptastic solver does it in ~860 seconds.

Also, it is my personal stylistic choice but the double for loops everywhere seems redundant to move around. It is more than possible to change your double for loop to a single loop as you are not even going, 3x3 example, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) - > (1, 1) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) for the most efficient path. So reduce that to math instead, On top of that your move_to code already takes into account the edge jumping you can do so wild to me that you didn't do this, again my personal view on it.

ws = get_world_size()
x, y = 5, 1
pos = x + y * ws
pos += 1
x, y = x % ws, y // ws

The above is the sequence you would use then you can just use a simple for loop to iterate over the entire board calling your move_to function with the (x, y)

for i in range(ws ** 2):
    move_to(i % ws, i // ws)

[Anonimi Angels]

@owenz The primary code isnt mine you can find the original author on top, about the timing it averages on 1< or < 10

[Anonimi Angels]

Originally posted by owenz:

So 300 iterations my craptastic solver does it in ~860 seconds.[/code]

Didnt even tried it with power, it may be even faster

[Anonimi Angels]

Ill measure the time and post the time of a single cycle of 300 iterations

[Anonimi Angels]

162.4 s

[N0ma13]

This runs around that speed as well. I need to test a 300 iteration block but so far I'm seeing most under 2.

def navigate_maze():
    directions = [North, East, South, West]
    move_offsets = {
        North: (0, 1),
        East: (1, 0),
        South: (0, -1),
        West: (-1, 0)
    }
    visited = set()
    path = []

    def dfs(x, y):
        if (x, y) in visited:
            return False
        visited.add((x, y))
        path.append((x, y))

        if get_entity_type() == Entities.Treasure:
            harvest()
            return True

        for direction in directions:
            dx, dy = move_offsets[direction]
            nx, ny = x + dx, y + dy
            if move(direction):
                if dfs(nx, ny):
                    return True
                move_back(direction)

        path.pop()
        return False

    def move_back(direction):
        if direction == North:
            move(South)
        elif direction == South:
            move(North)
        elif direction == East:
            move(West)
        elif direction == West:
            move(East)

    start_x, start_y = get_pos_x(), get_pos_y()
    dfs(start_x, start_y)

[Chin Music]

Originally posted by Anonimi Angels:

Ill measure the time and post the time of a single cycle of 300 iterations

How are you measuring execution time? I can only figure out how to measure the number of operations.

[N0ma13]

hmm looks like just over 3 seconds average with 300 iterations.
Not as good as I'd thought

[N0ma13]

Originally posted by Chin Music:

Originally posted by Anonimi Angels:

Ill measure the time and post the time of a single cycle of 300 iterations

How are you measuring execution time? I can only figure out how to measure the number of operations.

start = get_time()
do_yo_thang()
print(get_time() - start)

For a bulk run make it an array and sum up each iteration at the end.

[owenz]

Originally posted by Chin Music:

Originally posted by Anonimi Angels:

Ill measure the time and post the time of a single cycle of 300 iterations

How are you measuring execution time? I can only figure out how to measure the number of operations.

Just take an approach from functional programming and pass the function to a time_it function which, and as a possible side effect slapping functional programming's face, print's out the time it took.

Would like something like

def timeit(func, args=None):
    start = get_time()

    if args:
        func(args)
    else:
        func()

    t_time = get_time() - start

    quick_print("Time Taken: ", t_time)

    return t_time

Originally posted by Anonimi Angels:

162.4 s

I like that, I just never got around to fixing mine because it works.

I know implementing Dijkstra’s Algorithm or A* would work better than mine though.

Originally posted by N0ma13:

hmm looks like just over 3 seconds average with 300 iterations.
Not as good as I'd thought

The more iterations done with this maze the faster each iteration should get as there are less walls, but my craptastic solution obviously will never do that as it does not take into account where it is at vs where it needs to go. Need to work on it .

[acters]

Hey instead of a "Depth-First Search" I tried to implement the "Trémaux's algorithm" also taking this link as inspiration for reducing time of finding the treasure. https://openriver.winona.edu/cgi/viewcontent.cgi?article=1131&context=wsurrc
you can find my scripts for maze sunflower and pumpkins, and all the beginning crops. I also have a trade management system in place.
Note on pumpkin code: It will be slow without fertilizer, but pumpkins being the trade resource, you can wait one cycle for it to get enough pumpkins to start going fast with fertilizer!

so I suggest importing all of my scripts to prevent errors as the trade management should be able to farm the needed resources for whichever farm you wish to start farming for.
Also, you might want to lower the number of resources to get from each of the function calls to the trade management function for each farm. This is because it is set so that it can handle the max upgrades. lower level upgrades return less crops and may take longer for you to farm until you are able to upgrade to max. Another option is to set a set amount of resources to skip farming to test each farm out.
I normally will set my resources to 0 as I reach well into the millions very quickly for many of the farms. The reason is because the game will not display the entire number if it gets too big. I end up needing to set to 0 so I can see how fast the drone is and for testing the trade management function when I need to make changes.

About my maze solver:
There is a safety check to start the run in the middle of partially completed maze run.
Currently the first maze run will be sort of an exploratory one unless it gets lucky to find the treasure quickly, it gets faster as it progress with less walls on the map.
so it should have a top search time of less than a minute(<30 seconds), with sometimes finding the chest in less than 10 seconds, near the end with most walls removed it should take less than 1 seconds. Time is based on having all the speed upgrades max, and power resource to increase speed. Do be wary of slower speeds can increase time.
It really depends on which walls are removed during the first few runs through the maze. sometimes, the removed walls make it easier, sometimes they can actually make it harder to find the treasure as it will get stuck examining same areas often until it finds it way to a new area.
https://github.com/Acters/TheFarmerWasreplacedScripts

[owenz]

Originally posted by acters:

Hey instead of a "Depth-First Search" I tried to implement the "Trémaux's algorithm" also taking this link as inspiration for reducing time of finding the treasure. https://openriver.winona.edu/cgi/viewcontent.cgi?article=1131&context=wsurrc
...

About my maze solver:
Currently the first maze run will be sort of an exploratory one unless it gets lucky to find the treasure quickly, it gets faster as it progress with less walls on the map.
so it should have a top search time of less than a minute(<60 seconds), with sometimes finding the chest in less than 10 seconds, near the end with most walls removed it should take less than 5 seconds. Time is based on having all the speed upgrades max, and power resource to increase speed. Do be wary of slower speeds can increase time.
It really depends on which walls are removed during the first few runs through the maze. sometimes, the removed walls make it easier, sometimes they can actually make it harder to find the treasure as it will get stuck examining same areas often until it finds it way to a new area.
https://github.com/Acters/TheFarmerWasreplacedScripts

Nice, I redid mine and implemented a Greedy BFS and I am under 2 secs for each set, got that from 516 seconds for a full set with 300 sets so around ~1.7 seconds each. The first thing it does is a least walked path to discover the whole board, then passes that board info to the BFS.

This is even taking into account that every 100 sets I re-scan the board to find better routes, best isn't even a consideration for me lol.

If I can get my BFS search down further it would be faster as there is a good pause between each set as it is calculating the next route. Though I do notice that it takes about the same time to get to one 1-2 tiles away so has to do something with all the OOP going on in my code.

https://github.com/zeziba/farmerwasreplaced_testing

[acters]

I had a bug with how I did my timing and realized I never refreshed the start time when the treasure chest was found and just used the start time from the very first run. So instead of <60 seconds, I should have reported <20 seconds. with it getting less than 1 seconds at max speed with power resource. so sorry for the confusion.

I just got done timing the algorithm and notice it takes for a Total full maze run about 331.8 seconds. so while it is quite fast, it does waste plenty of time searching as the algorithm is meant for searching unknown mazes. yet another run total run took 477.37 to complete. This is wild swing in completion times is due to luck on whether or not the search find the treasure fast or ends up stuck in the same areas. so it is not perfect at all!
NOTE: this is for a 10x10 maze!

I could realistically just map the entire maze and use a* to get to the treasure faster as searching for removed walls is slower than just moving even if it travels the long way around. moving is just always faster.
I just wanted a challenge to implement this algorithm as the star of the show. since this algorithm is meant to search each path and find the fastest route after it is done. however, the way I implemented it here is meant to search around for an object somewhere in the map, instead of its intended purpose of traversing a map from one corner to the exit on another corner.

also, could do a hybrid were it uses a* for n number of runs and then will redo a search for walls since many more should be removed that it is worth to waste time checking the walls if they were removed.

However, there is a noticeable drop off in performance if you have to map really large maps, which this games does not have but still hear me out. for my algorithm, it will likely take less time for the Trémaux's algorithm to solve larger maps than mapping then using a* to find the shortest path. however this is based on first run basis. for each iteration, the a* will be always faster as it will have the map memorized. So maybe I can create an alternative maze solver that maps out the area then uses a* with periodic mapping out the maze when enough walls are removed. with only 300 iterations, it should map the maze in the first 150 runs occasionally then afterwards will slowly reduce the amount of times it will map out the maze to not at all as it gets closer to 300 iterations, after all it is usually faster to move than it is to search for missing walls.

[acters]

one idea I thought about implementing, but can't figure out for now, is to have the drone memorize "paths" or areas in a way that it knows if the treasure will be in an area and to travel towards the treasure without accidentally going the wrong way. there is plenty of wasted time on it searching around for the right path, because it heavily relies on Trémaux's algorithm principles. when it should be able to path find from the memorized map of the maze.
plus, there is also the trouble of having to deal with areas the have no walls.
As even more walls are removed, the map becomes more open. The idea of memorizing paths is less needed in the later iterations as this algorithm will try going towards the treasure's direction instead of needing to memorize paths.

[owenz]

Originally posted by acters:

one idea I thought about implementing, but can't figure out for now, is to have the drone memorize "paths" or areas in a way that it knows if the treasure will be in an area and to travel towards the treasure without accidentally going the wrong way. there is plenty of wasted time on it searching around for the right path, because it heavily relies on Trémaux's algorithm principles. when it should be able to path find from the memorized map of the maze.
plus, there is also the trouble of having to deal with areas the have no walls.
As even more walls are removed, the map becomes more open. The idea of memorizing paths is less needed in the later iterations as this algorithm will try going towards the treasure's direction instead of needing to memorize paths.

From the site you linked to the modified Trémaux maze solver if the connectivity of the maze is low it will be able to solve the maze faster. No idea what the actual % is for a wall loss at each try but it is safe to say that after 299 iterations around 80% of the maze is missing if not more. So there would be some inflection point where Trémaux's solver would perform best over a memory of the board using any of the other solvers as for this game each action cost a basic unit of "operation" which drastically slows down the process. So it is highly likely as how this performs it's search that it would stomp any of the other competitors once the inflection point is hit. Though this would require some testing.

To test it, simply generate a map and start a solve w/o a harvest or fertilize and then time it. Reset position to start and attempt again with a different algorithm, as each algorithm is essentially deterministic, you can just use it's initial solve time as a good comparison. If there is any randomality will need multiple runs.

Then get to 100, 200, 300 iterations and test there, can check in smaller increments when the inflection window is found. It can be checked mathematically as well. Using the get_op_count() each set takes ~30k ops with a min seen at ~18k and max of ~32k. I simply do not think that your algorithm should be any where near that op count as you are not building and passing around "huge" data structures and then walking those data structures to find the path. So there is an absolute min that any of the A*, Dijkstra or anything else that involves manipulating a data structure as the game imposes a min of 1 operation cost on almost every operation will be beaten by anything solver that doesn't have to go through all that.

As a strict note, there is NO cost savings in op cost using A*, Dijkstra or BFS as the data structure has to be built and traversed and that cost "OPS", so with a board with high connectivity or low it will still take roughly the same time to solve unlike your algorithm as it will lower it's "OP" cost as time goes on.