Welp, It's Time for Solving a Maze with Python
HTML-код
- Опубликовано: 23 май 2024
- Program and optimize a drone to automate a farm and watch it do the work for you. Collect resources to unlock better technology and become the most efficient farmer in the world. Improve your problem solving and coding skills.
Check out The Farmer was Replaced here:
-- store.steampowered.com/app/20...
Check out my Python tutorials:
• VARIABLES, TYPES, AND ...
#games #olexa #strategy #farming #automation #programming
Thanks for watching!
-- Extra Olexa Content - / @olexa2
-- Discord: / discord
-- Twitch: / olexastream
-- Twitter: / olexayt
-- Reddit: / olexa
-- My Nexus Gamestore: www.nexus.gg/olexa
-- RUclips: / olexayt
-- Business Email: olexakid@gmail.com
-- Join this channel to get access to perks:
/ @olexayt
Music I Use:
-- www.bensound.com/free-music-f...
-- Spring by Ikson
-- Harris Heller Streambeats Lofi 
Игры
I love how you started off explaining how to get through a maze so well, and then proceeded to entirely ignore it and say go as far as possible rather than hug the left wall.
I think from the start, if he simply kept the image of holding out his left hand and imagining what his hand would be touching as he walked, it would have been much faster to conceptualize
I feel proud that I fully comprehended the problem playing on my own despite not knowing how to use lists to write out the solution.
Like somehow as a non-programmer I knew exactly the tools I would need I just had none of the experience necessary to utilize them
Following a wall might never get there if it's in an island
@@3zdayz that's true, but the description states there will never be any loops on the first maze iteration, so there will be no islands
@@myclamish except in the bonus mode where walls get removed when the chest moves... Then you end up with big open areas too
my solution has about 10ish lines of code... while you're not over a treasure, move randomly till you are... then harvest...
given an infinite amount of time, it solves any maze :)
Lol this is psychotic, and I think I love it
If you like this game, I highly recommend Turing Complete. It’s a tutorial in low level computer architecture and programming disguised as a puzzle game. You start with a NAND gate and eventually end up making your own assembly language. Each logic gate and module you make can be reused later to create more complex systems. It makes you feel like a genius because of how approachable it is.
It did not make me feel like a genius because reinventing assembly from scratch using binaries is pure madness and I rage quit when presented with that ungodly interface.
pretty sure the "coords() in visited" issue is because "in" checks if that exact object is in the list, not just an object that is equal to one in the list. it may work if you have coords() return a tuple instead of list, otherwise you'd have to iterate over visited to check each element manually
Thats exactly it, coords() is an object, each time created has a different address in memory even if the content is identical
or combine cords into single number like get_pos_x()*get_world_size+get_pos_y()
Oooooooooo interesting yup that makes sense. That’s why ‘not in’ works but ‘in’ doesn’t
classic reference vs value. I was screaming with my inner voice, knowing I could never help Olexa during the video
Interestingly normal Python would work completely fine for this. Just ran the exact same code on my PC in a Python window and it worked perfectly. Hence my confusion haha.
It was really funny seeing you go in circles for ten minutes and then suddenly solve everything
Welcome to programming
Lol😂
I actually tackled Mazes before doing sunflowers (and ended up being surprised how easy I was able to do Sunflowers when I did get around to it). Of particular note, and this tends to get missed unless you're actively tracking it, is any "failed" attempt to "fertilize" the treasure chest does NOT consume fertilizer, meaning once you've got the initial maze, you only need 299 more fertilizer to get the maximum amount of reuses on a maze. This equates to 2990 pumpkins, which is about 7.6 pumpkin squares of side length 7.
My solution to doing 300 solves was actually to map out the ENTIRE initial maze (and noting where the Treasure initially spawned) as a 2D List of directions away from "start" and then just use the map I stored in memory to go from "start" to Treasure, measure the next location, fertilize the treasure, and return to "start", ignoring the possibility of any removed walls. This does allow me to get all 300 solves with the caveat that I will never get a "shortest path" from one treasure to the next or even from "start" to any given treasure after a certain point. As such, it can DEFINITELY be beaten in efficiency.
Next on the chopping block is Cactus, which is... a bit simpler than I expected it to be once I made a realization working it out in EXCEL, though having knowledge of how some simple algorithms work helped.
Yeah, whole point of reusing mazes is about removing walls, so paths to the treasure can be shorter. But you can't hug walls anymore.
My solution for reusing the maze is that I explore the entire maze first, and save all the directions you can go in each square, then do a virtual solve where I effectively just follow the right hand path but using the bots memory instead of physically doing it. Then every time I reach a crossroad due to backtracking I prune the path back to that so i don't waste movements.
I solved the maze using a modified trémaux’s algorithm that I handcrafted. Its very fast and I didn't worry about returning to start or holding on to the memory of the maze. This means I can stop and start the maze solver at any position with any map size. You can use measure() on the treasure chest to get its next location but without knowing the location, I default to trying to reach the middle. It does not care about staying in the area of where the chest is at. it can move across the entire maze in the opposite direction or eventually reach every corner of the map.
Just a real small thing with the pumpkin fix, the do a flip should be under the can harvest check, else it will always do a flip even if it is ready to harvest right away
Another problem coild be if last planted pumpkin dies, you're checking only if you can harvest, not if you have a pumpkin. In that case you'll flip forever.
@@Firegregor1 Yup, the last while should have both entity type and growth checks to make sure there is a pumpkin and it is mature in case the last pumpkin dies before maturing after the last check of the previous loop and replant one if so.
The part about 'no cycles' means that the original maze will not have any disconnected loops that form a cycle, so a follow the wall method will work on a 'fresh' maze, but as you redo the same maze, walls can disapear and allow cycles/loops.
That's what it means, but I found that it was a lie. There is a chance that a freshly generated maze CAN contain a loop. It's pretty rare from my experience, but I have seen it happen many times.
@@Plystire I have yet to see that situation myself, all my loops I have seen on my maps are from 2-5 iterations in
Current stats:
Video was uploaded 30 mins ago
Already has 47+ likes
200+ views.
Still confused as to how this series is going so well... Especially since it's literally a coding series, which is not known to do well on RUclips for continuous content's sake.
Keep it up olexa
We love watching Olexa struggle, duh.
I am having fun, since my coding skills are, as a 14 year old, about as good as olexas and it is fun screaming at my screen what he is doing wrong, and being taught in the same video
Drone go speed speed.
One of the reasons is the game-afycation of it
Engagement is wild when backseat gamers and backseat programmers intersect :P
Instead of adding 'if x == 4: x == 0' and 'if x == -1: x = 3', you could use modulo.
'(x + 1) % 4' and '(x - 1) % 4'. This ensures the numbers stay within 0 and 3, and "wrap around" correctly.
Although we know there will always be just four directions, you could add '% len(directions)' instead of '% 4' to make it programmically better.
Edit: you used modulo correctly at 37:50, but didn't use it earlier, or right after when adding the additional x ++ 1😅
Lol I wasn’t thinking but you’re absolutely right
I think the reason why your pumpkin code breaks is because the last pumpkin you're waiting for disappears when it is fully grown. As well as checking can_harvest() you should check get_entity_type() and replant a pumpkin when it disappears.
Loved watching this and seeing the way your brain works. My first attempt at this was to send my little drone pal on a random walk until he found it. Really simple to code, really inefficient, but so much fun to watch.
If you adapt `goto` to be able to handle not moving right, then it can look something like:
- plant the maze
- follow the wall to find treasure
- measure the treasure to see where it will go next
- fertilize to move the treasure
- goto(the measured target)
- harvest after 300
I've been dealing with this one myself last night, and I found that the best way to do it is to first do a breath first search algo in order to find the position of the treasure chest. then after you've found it, you create a floodfill distance array and create logic to modify the flood_grid, when a wall is found. You use this method until you solve for a finished floodfill path, then simply use the same path over and over for the 300 rounds of the map. The initial solve takes the longest at about 16-30 seconds. the floodfill solve takes 4-8 seconds, while the pathing directly with the flood fill grid is basically a 1-2 second trip.
jea that ill do
but imagine a maze with an already existing loop, so you are able (re)start at any time
probably using an array instead of a list...
@@vinc0511 If he stores initial maze wall positions, there are no loops. Loops only appear once walls start disappearing, and if he already stored what walls, he will ignore walls that disappear.
bfs first? i feel like thats a lot of wasted moves spent backtracking. if one continuation is on one side of the map, the other might be on the other side. With how small the maze is, there is only one "long" incorrect direction which is usually the first turn. dfs will guess the correct direction at least 50% of the time. maybe more with flood fill. you'd have to test it, but i feel like dfs would be faster in these mazes
oh i misunderstood. youre using the same path over and over. so u want to take the little bit of extra time to get the shortest possible one. I was thinking that you'd want to rerun the search function as the walls dissapear. nice.
The point of reusing the maze is that you can map it, then you just have to find the path to the chest fertilize it 299 time then harvest it.
It is faster to map then go through the maze to a location you know than to explore a different maze everytime...
Once you have the maze mapped just use a Breadth first path search then queue movement and loop it to get to the chest, it is a lot faster this way than random guessing the direction/path, you can also add a condition to remap every 50 loop or so to add shortcut, but that is only to raise your efficiency, the first map should always work if you map the whole maze ...
Also, the in doesnt work on list the same way it work on dictionary, I think the list check for the index which is why the for loop work on list
I dont think Breadth first search is the key here as everytime you want to explore just one tile you would travel through the same tile many many times.
i would go for Deph first search
I completely forgot that you can know the next location. That makes total sense now to use a DFS algo for this.
@@xdesiek1005 He's speaking of subsequent treasures in the same maze -- so once you've mapped the maze into memory. At that point you can use any algorithm you want without loss of efficiency, as you can check any tile's condition without visiting the tile
I just did a pseudo-DFS for subsequent runs through the maze, prioritizing movement directions attempted based on where the treasure is from current location. Works great, and always uses shortcuts.
Your "lucky" algorithm is frustratingly elegant and awesome, man. Nice work. Combined with auto creating the next maze, it is much more entertaining (and quicker) than what I was doing. haha
when i got to the mazes i had no idea what to do about it and just made myself 'buttons' for moving up down left right and harvest to manually solve them for treasure 😂
I've been stuck on mazes for a while now, super impressed that you solved it in 20 minutes!
my idea for the maze is have the walls be 2 2d lists, 1 for vertical and the other horizontal, then fill them by mapping all directions, going back (direction[(i+2)%4] ) if the move returns true.
once the lists are built, you should be able to move by just using a function that browses the whole labyrinth in a loop blindly, checking if a chest was found on every move
this isn't the most efficient as you don't exploit holes created, but it shouldn't have any issues with loops.
an other option that can be combined with the previous one would be using your algorithm but adding a "visited" array and treat trying to go into a visited node as a pseudo wall and try all the other directions first, going from least visited to most visited (increment the visited value by 1 every time you go through, and reset to 0 when the chest is found.)
I think the most efficient option would probably be to use the first algorithm and reupdate the map using the 2nd algorithm every like 15 chests or something.
Since measuring the chest gives the location of the next place in the maze the chest will go, you could do do left_first_search for the first chest and a different algorithm for the later chests. Maybe A* or build a tree representing the maze... or whatever's less effort
Totally forgot that using measure on the chest tells you where the next one is. That changes everything haha
This game is so awesome! I got recommended your channel through one of these videos and have since binged every episode. I’d love to see more coding games on the channel.
Commenting before finishing the video (a classic bad move): at 25:33 I think I learned how I would do it for following the left wall strategy.
Imagine we've just successfully moved South, and we want to check for a U-turn to the left (East), then try to move East. If you can't move East, move South. If you can't move South, move West. If you can't move West, move North.
Each direction gives priority to the direction one step counter-clockwise, and then proceeds clockwise, or counter-clockwise if you want to follow right side.
I would only be able to setup a clunky brute force way, but I'm sure you could get it to set a variable to it's last step direction, pass that into some function and then try each direction in that priority order. After each successful step you just check the tile below you to see if it's the treasure. Smart people in the comments let me know if that makes sense.
Fun vid. The part where you have to look left after moving is where the whole trick is.
I solve the whole maze, save the path, repeat the path forever, while fertilizing
At 13:40 ish when you said hug the left wall I laughed so hard cuz I always do the right wall instead and technically the result is the same either way, but in this case the right wall would have been a much shorter path
My solution was to first use a wall follower to map out the map. Then with knowledge of where all the initial walls are (and the location of the first treasure), I would perform a reverse breadth first search for every coordinate to create an array that, when given the current and target coordinates, would tell the robot what direction to move (for a 10x10 maze, this equates to a 10,000 element array). The initial calculations take a while, but after that it speeds through the actual solving of the maze. It completely ignores the lost walls, but it's not like the longer paths take all that long to traverse.
I am also a developer in my main job, I solved this before watching this, and I loved to see you made the completely exact errors like me 😂
Probably someone beat me to it, but the problem with the pumpkins *now* is that youʼre assuming that the last pumpkin will survive. If the last pumpkin dies you get caught in a loop of waiting for a nonexistent gourd to grow.
12:25 Fertilizing a treasure does *not* use up the fertilizer if it fails; fertilizing a hedge does. Also, the other reason to care is time optimization. The treasure in your current maze is at (2,4). Suppose you get there and run `measure` and it says (2,5). Then itʼs just one move to get to the treasure, instead of a whole new maze. (Alternately it might be really far away and you know you want to restart). The downside, as it points out, is that many maze-solving algorithms rely really heavily on “no loops”, so if youʼre doing something like “always turn right”, youʼll get stuck in re-used mazes.
(15:00 And now weʼre at the point where youʼre actually implementing solutions, instead of preamble, so Iʼm going to stop for now; if I have more comments Iʼll reply to this one tomorrow).
I ended up not even trying to reuse mazes, despite explaining above *why* it could be useful; pumpkins are cheap. I donʼt know how long it would take to do good code for a maze with cycles (without looking it up); most pathfinding algorithms I can think of assume you know the whole layout, and mapping the maze would be annoying, especially since to really take advantage of it you need to check when walls are removed and update. In the process, though, I found that a treasure will never “move” to the spot it was in originally, but if you get lucky it *can* spawn right under you when you create the maze.
54:35 I *definitely* did manual maze solving and included a thing to make manual maze solving easier (it reads a string so 'E3SW2' would do what you did). And since I can see the entire maze, I can take advantage of knowing the path and of reusing mazes much more easily than even a perfectly programmed drone. For getting lots of gold it for unlocks and cactii you still need an automatic version, of course, but having a good manual solving tool is quite helpful.
Tip: the game writes an output.txt in the game install directory with the contents of all your print() and quick_print() lines.
I had mine do sorta like a random walk, except constrained by the walls, so it would return to the last unexplored node when it hits a dead end and continue from there.
This wouldn't have any issues with cycles since it only attempts to move into unexplored paths. This only finds the treasure the first time though.
I believe I'd have to alter it to scan the whole grid first to set up the graph and then use a* to generate a path to next treasure position, but I don't really want to bother implementing that yet lol.
For coordinates I usually just use x*10+y since apparently the max grid size is 10(unless there's some way to go higher, apparently in old videos you could). You could also use x*grid_size+y but that'd throw off your coordinates if you buy the expansion upgrade. Then if you need to break it back down to x, y it's coord // 10, coord % 10
My approach for this was a recursive DFS with a little memory of where I've been so I can break cycles. Since I'm not mapping the walls and I actually have to check stuff by going to the place, DFS is faster (DFS is always better for the first maze because there's no map and BFS has a lot of backtracking which leads to more redundant moves), but when I add a mapping functionality, I'll probably use Djikstra or A* to virtually path to the treasure and just do the exact moves needed to go there.
Got pretty stuck on the maze... I had the directions in 90 degree increments in a list... knew that when the move failed I needed to change direction but didn't consider that I should change even if it succeeded to check that the wall is still to the right.. thus quite often I would get stuck in loops... Algorithms are tricky!
Great video!
Love the series, hope the yt algorithm is doing you well
Man. That's am elegant solution to the maze. My code is so long and complex. It'll check all four directions for a possible move, then pick a direction and move that way until it meets a fork, saves that location in a list, then repeats. If it meets a deadend, it goes back to the most recent fork and pick a path it did not go down and do it again. It keeps track of all of the coordinates in a list so if it meets a deadend in every path from the start, it will follow it's path back to the start and go the other way.
Nice job
That tracking sounds useful for when you want to reuse the maze tho
If I understand correctly, you basically implemented a Depth-First Search algorithm (DFS), which is really impressive if you’re not a programmer, and should work for all cases (not the fastest but works great) ! Congrats!
Thanks! I am not a programmer. It works 99% of the time, something breaks somewhere, which I haven't tracked down yet. But when it does break, it just starts over and eventually figures it out. It is quite slow though, yes. Usually takes the longest possible path.
@@user-yd7ug3jb4t I'd recommend "debugging" like he does in his videos, printing different things in different condition branches, so you're sure stuff gets called, and know what value it has ( ex. print("Pumpkins : ", num_items(Entities.Pumpkin) ),
this will help you understand and get more familiar with what's actually going on in your programs (It's how I solve 99,99% of my bugs honestly).
To make your code more efficient/readable, or just get some tips, look at some DFS videos on youtube, or some pseudocode on wikipedia even helps.
@@user-yd7ug3jb4t And once you got DFS figured out, you could try and implement BFS instead (Breadth First, like expanding by a bigger and bigger radius, instead of going down every path first, aka Depth First), which shouldn't change too much in the actual algorithm (normally, you just need some priority queue, instead of a list of points you backtrack to, It's been a while so I might be misremembering).
I don't think Dijkstra or A* is possible from how I understand how the game works (at least not a straightforward copy of the pseudocode, but maybe some ingenious implementation), but you can also take a look at those algorithms, if you basically want to know how google maps works (It uses A* if I remember correctly, but they also might have found a new way), and a lot of networks nowadays (virtual and physical, like the internet or mobile networks) . Sorry for the info dump x)
Thats only how mazes work for the most simple of mazes and granted a maze with an entry on one side and an exit on the other (wether that be directly opposite or any other location, by other side i dont mean spaciously on the other side, its basicly a graph of intersections if you simplify it down to the math behind it) and "the other" is in space at the outer wall of the maze then its likely your maze will be that simple, but if you want to find something hidden in the maze it is much less likely to be that simple, espacially if it may have loops, meaning that you can come back to a location without literally taking your steps backwards.
Your algorithm is good, to solve problems with loops is to detect loop and if loop detected then change rule from right to left wall tactic. You can imagine loop as circle and depending on the direction that you go on this circle right and left is inside and outside of this circle. If you stick to right side of the wall the you will visit all branches in or outside of the loop (you can see this on your video the very time you go in to loop you visit only outside or inside of this loop branches). If you detect that you are in loop and you have to change to stick not to right side but to left side.
Hint to detect if you are in a loop you have to check if you enter any position 4 times (you can try thinking about this.)
Okay, so two simple ideas for the maze:
1 - (What I did) hug the wall until you find the treasure. Then now that you know the destination, do a depth first traversal of the maze prioritising moving towards the treasure.
2 - Map the entire maze (including the location of the treasure so you know where it is at the next stage) then in memory solve the maze using whatever method then follow the path.
1 has some inefficiencies in terms of going back into dead ends each time. But further along as more and more walls are removed it becomes better and often makes a bee-line straight to the treasure.
2 has a penalty of needing to map the entire maze first, but then can use memory solve the maze (much faster than moving the robot), but as more walls are removed, it will still pretend they are there meaning near the end it can be taking quite inefficient routes.
Your last implementation was kinda good for some tasks, don't try to solve too hard problem, just reset. You could do a limit on moves, say do 3x the moves from field size, then reset the maze
While doing the initial mazes I probably would have moved the drone manually to get to the treasure to unlock dictionaries. I'm not much of a programmer, but as a gamer that seems far simpler than coding a workaround that lasts one episode.
This one is going to be a fun one
just found you and binged the playlist, so i hope there is more to come soon.
its been a week so you probably already solved it, but if you want to make it smarter at breaking loops while staying with a similar solution, I think it needs to check for a sequence of previous spaces instead of the individual space. when it doubles back from a dead end it freaks out because it already saw that space and tries to 180. if you had a list of the last ~4 spaces in order and compared that to visited it would get fewer false positives on loops.
something like
visited = []
recent = []
move(directions[x])
recent.append(coord)
if recent.len > 4:
recent.pop[0]
if recent in visited: (probably need to reword the 'in visited' in a way the game will accept)
Yeah, I kind of lucked into a working hug-the-wall algorithm myself, at first I was making an array to record which direction I went at each spot, then realized I didn't need it and just had it have a direction, try to move, if it worked, turn one direction, if you didn't move, turn the other direction. Didn't even try to re-use the maze as I didn't see much of a point unless I could learn how to write a pathfinding algorithm. Mapping the maze wouldn't be too hard, but the pathfinding would be annoying and it's not something I've done before.
i had to laugh at 17:58 when he said "thus i have to go as far north as possible" after earlier having perfectly well described what "keep hand on the wall" means, completely ignoring that you can't keep the hand at a wall when passing and ignoring openings ...
edit/hint : even when you start straight=north, the rule does not say "move straight first" but "move left first" or "move right first". and during all the algorithm, the direction for "straight" (and thus also for left, right and back) changes, and moves need to be done according to those rules (using left, straight, right, back) instead of fixed compass directions.
ps : i did the same error at first, but after noticing that different between relative directions and absolute directions, the next attempt worked perfectly. I'll only have to improve it now to use more effective commands and data structures after researching dicts.
Ive been putting off solving the maze myself to watch your omega brain solve it
I feel like the measure() command will be helpful once the walls start disappearing! Not a programmer, but I've been loving learning some coding with this series. 😄
I think rather then storing every single coord that you are visiting instead keep track of the coord that you start at and then check your coord after each move to see if it is the same. I think this will work as you wont be able to enter into a loop that does not contain the location of where you started after collecting the treasure so your either guaranteed the chest or a loop. From there you just need to make the other changes to get out of the loop.
idk if someone else mentioned it. but [shift] + [tab] undoes the tab of selected lines. if the steam overlay activates, then change the keybind of one of them.
either harvest the treasure and replant each time so u dont have to worry about cycles or use floodfill algorithm for mazes with cycles
I just made my own maze solver using a modified trémaux’s algorithm. It is very Fast and flexible, and finds the treasure at any map size and was able to find that there is a limit to how many times you can fertilize the treasure chest. lol
Bro you can techincally do a depth/breadth search, just make him go in one direction, note the directions it could go, and go back. This will be a many dimensional list if i am right, but ig it will work
Here's my brain thinking,
A list with your directions
A variable that stores your initial direction when you can move
A list that stores all movements from the initial
When you move north it has a check that prevents south from running until last. Something like if initial x = x + 2 then x = x + 3
Then if you have to move in x + 2 direction then move back through the list of directions each step checking the 2 directions that weren't checked before. Example like if we came from north and the next move is west we know to check east and south.
After doing the check for each direction of movement we need to remove the movement from the history list and add the new path.
If the history list is too big we know we are in a infinite loop situation and can check other locations.
The pumpkin sometimes fails since theres a small chance it will die after the "is pumpkin" check and in the while loop youre not trying to replant
i belive that any kind of search or pathfinding in mazes should be done after researching all the "good data structures".
thus first do the simplest method ("lefthand follow" or "righthand follow") to go to the treasure a few times without reusing the maze, to earn some gold.
then research dictionaries or whatever else is needed and requires gold. and only THEN care for doing better algorithms when needing that in the endgame.
btw: only few drone actions (successfull(!) moves etc) cost 200 times more time than most other commands (this is in the help popups, but often overlooked)
I adore this series
If drone visited starting square twice then move normally and make first possible square start location. I think that works better.
Sadece tek bir kare başlangıç karesini tekrar ziyaret ettiyse o kareyi başlangıç noktası yapıp tekrar denemesini sağlayabilirsiniz.
nice job! as a non programmer, this is beyond me lol. I might just try to borrow yours... or modify it maybe.
aMAZEing episode)
I’ve never done programming and this series is literally the first time I’ve tried to understand programming, I was wondering, can’t you keep track of how many looks the function does before it find the treasure then +3 to X if it hits an arbitrary number that would be unlikely to happen without hitting a chest? So something like after 55 loops without finding a chest, add 3 to X.
Very farming video. 10/10
Realizing this after watching and reading comments, this is literally the micromouse competition
Only difference being the micro mouse can save the coords and see 😂
Only difference being the micro mouse can read coords and see
I ended up writing my own maze solver that takes a localization pass then keeps runnign that loop. I want to optimize later so that it knows where the branches are and can evaluate the branches for where the treasure is and skip any branches that don't have it.
btw you can use energy to upgrade mazes to get more gold from the treasure
I didn't realize move() returned a value. I've been checking coords before and after the call.
idk shit about programming but asking anyway, there is a way for you to track the quick_output?
like ask for output with 50 moves made, make a list and attribute a number in that list for that output result, if found chest = delete list,
if not= ask for output with the next 50 moves, if the output (and by that the number) is different, continue
if not and the output (and by that the number attributed) is equal = move in a different way (some x and y magic that you do)
u can literally make a list toadd this stuff in
Remember that you can use measure() to know where the next treasure spawns at.
this is my maze solver for a maze without the loops in it ( I think its pretty simple ):
def MazeSolve():
Directions = [East, North, West, South]
current_direction = 0
previous_position = [0, 0]
while get_entity_type() != Entities.Treasure:
move(Directions[current_direction])
if GetXY() != previous_position:
previous_position = GetXY()
current_direction = (current_direction - 1) % 4
else:
current_direction = (current_direction + 1) % 4
harvest()
up until now ive been assuming everyone meant maizes when they were talking about mazes, and just assumed corn fields were spelt like mazes and not maizes
For the engagement! Let's gooooooo! 🎉
You keep mentioning that your problem is that you move too fast early on in the video. If you buy the benchmarking unlock you can set your drone's speed manually to slow it down when farming pumpkins.
Also later on when you're having trouble with finding coord in visited, try making the return value a tuple by putting parentheses around the pos x and pos y. Currently you're having it return as a list of 2 numbers. Lists are created by reference so it has to be a list with the same name rather than a list with the same contents, but coords() always returns a new list.
Harvest 1 at time loops break hug theory
I would try it with a tree graph :D
But the implementation might be a pain.
Unfortunately I can't afford the game right now, would test it else by my self.
For testing "IN" use sets instead of lists in this game. That'll do what you want
could modify your pumpkin scrpit so it has a can_harvest that adds one to a count, that has to be equal the get_world * get_world in order to harvest
You could exit if you make a certain number of moves since the last treasure found. This would be a dumb way of handling cycles
For the record:
"in" works only with dictionaries and sets not with lists.
And as far I can tell this is intentional.
Also... BOI! I was expecting a similar else if abomination like your goto function but that while loop is almost elegant solution lol!
But… it… did work… for ‘not in’… lol
It worked for `not in` because coord() gives back the value, while in lists `in` searches for address in memory, rather than a value i suppose @OlexaYT.
@@OlexaYT It defaults to False / None negated it is True...
It was triggered every time with every execution.
So I literally just tested all the things of "X in List" I could think of in the game itself and I'm pretty sure I found exactly why it wasn't working as Olexa wanted it to:
for X in List works (and the ingame documentation actually explicitly uses this as an example for the documentation on Lists)
if X in List also works as I would expect it to UNLESS X itself is a List.
if X not in list also works as I would expect it to UNLESS X itself is a List.
Now, the documentation doesn't mention if X (not) in List for the List documentation (instead relegating that to the Dictionaries documentation, which DOES include sets). But doing if X in List still works, even though it's possible that there's more than one instance of X in a List as opposed to a set.
The issue is how OIexa was storing the coordinates. Rather than use tuples for a given coordinate ("(X,Y)" for instance), he's storing them as lists ("[X,Y]"). This causes a slight issue because in that case, the check is if the list object itself is in the list.
Olexa had a (theoretically) viable idea, but his earlier grudge against tuples came back to bite him on this one.
Yup understood now! Nice catch
Now you have 2000 Treasure so you can get the Dictionary Commands and use that instead.
Also, couldn't you just reverse the direction of drone once it cycles? Example being your code at 28:36. This code resets the drone once it hits x==4 back to 0 which makes the drone keep hugging Counter Clockwise but if you had a code embedded after that block to say (# means I jumped down a line) -> x -= 1 # if x == -1: # x = 4 -> This would make the drone rotate Clockwise to hug the center of the cycle. You'd of course need a check outside that embedded loop to make the drone go x += 1 to have it go back to the previous direction so a -> if x == 5: # x = 0 -> would be needed but this should basically rotate you hugging the left side then after whatever parameter you set, have it rotate hugging the right side then break to hug the left side again and once the parameter is reached on the left side loop, go back into the right side loop. Rinse & repeat. I'm not a coder and all I know about python is from this series but I hope this works! Sorry for the novel.
not optimal but very well working solution to repetedli use the same maze took me about 100 lines of code and i needed map and bfs functions for it with map being used to create graf representing original maze and than used the bfs to find path to travel between the treasures gives about 150K treasure per run (and yes i did use the algos without proving that they work and i am not ashamed of it)
Ah, the visible confusion of someone only just reading but not quite grasping the documentation:
Simple test:
//we can track that we moved east...
direction = 0
if (move(East)):
move(West) //we moved East so we know we can move west
direction += 1
...modify some variable so we know we can move east from here
if (move(West)):
move(East)
direction |= 2 #I don't know if python has binary operators
if (move(North)):
move(South)
direction += 4
...etc...
We can now breadth-first search if we'd like by storing coordinates, or building a graph
For hugging a wall, pick a starting a direction, crash yourself into a wall, then repeat the following:
check if we move successfully to 90* of our chosen direction save that as our last known direction
otherwise if we fail check in the forward direction if we fail rotate 180*
while move(direction[x]):
pass
#we know we just failed to move in x direction
hug_wall = true
#fail-over case
while hug_wall:
t = (x + 1) & 3
r = (x + 2) & 3
if move(direction[t]):
x = t
else if move(direction[x]): #the hug wall direction, if we fail this
#
else if move(direction[r]):
#this now is like rotating around 180, your algorithm basically works until this point
# you checked this direction but stored the wrong heading, if you head in direction x, you need to test x+1 & 3 next, that's your "left" or "right" wall now
x = r
else
hug_wall = false #we're surrounded
This will still fail though due to cycles, so you do need something smarter.
Yo, I enjoyed this video
I guess you just use your method on the first run, then measure the treasure, then A* on the following runs. I'm not a programmer myself, but with the help of ChatGPT, I implemented a DFS function and it's kinda bad for the repeat runs, especially towards the end of the 300 repetitions, when there's hardly any walls.
Ok, I got a little mad when you said you needed dictionaries to have "numbers corellating to positions" which is literally what lists can do haha 13:57
It’s a pain in the ass to do though
Isn't it just a 'list = [ North, West, South, East ]". And the indexes are your numbers. Am I wrong? Or you meant something else
P.S. I wanna take the time and let you know that I and probably all the viewers appreciate the videos you make and that you interact with people in the comments.
Cheers :D
Oh for that yes that’s easy to do in a list. I’m talking about basically storing a full grid inside of a dictionary. So a 2x2 grid might look like
[[{‘x’:0, ‘y’:0, ‘plant’ : ‘grass’}, {‘x’:0, ‘y’:1, ‘plant’ : ‘grass’}], [{‘x’:1, ‘y’:0, ‘plant’ : ‘grass’}, {‘x’:1, ‘y’:1, ‘plant’ : ‘grass’}]]
I solved it by tracking the in game timer. if it hasn't found the treasure in 2 minutes: reset
I think before you have dictionaries, solving ONCE per maze is probably better. Simple code is just nicer to look at, and runs better. BUT. Once you have dictionaries, and can do the fancy things you smart educated types know, then it's probably WAY better to use known algorithms and just fertilize 300 times. Make a list of the map/walls, solve a bunch. Use measure() to know the coords of the next location.
Pumpkin is getting stuck when last replant dies. How about replacing flip with a plant fertilize harvest loop
I don't think you where missing something there was a patch yesterday that fixed something in the in qualifier where it didn't treat lists and tuples in lists correctly.
Oh nuu! Let's get this vid to 1000 likes!
Make another list that has the opposite directions of the direction Coming from and then let him ignore that direction and only try other directions
I hope you were thinking about it in your head 0:16
I don’t know if it was a coincidence but when he said “I’ve got Siri on my phone talking to me” Siri had activated just before that on my phone.
Edit: just replayed it. At 22:02 when he says “so you’re gonna check” it sounds like he says “Siri you’re gonna check” and it activates my Siri 😂
Sorry 🙃
Can you have it pick a random direction between 0-3?
That’s definitely a solution, albeit a pretty bad one haha. It’s probably good enough though
@@OlexaYT I was curious if after it repeats every position around a loop you could have it pick a random direction to try to get it to find a way into the parts of the maze it can't get into.
I have zero coding experience, I watched your videos in awe and fumbled my way through planting carrots! lol.
Just spitballing - coords() returns a list and not a tuple, right? I wonder if the semantics of 'in' doesn't work for lists (it should?) Weird.
That *was* the issue. It was comparing by reference not value. It’s been since changed in the last update
47:00 aren't you missing the "()" after the return?
Don’t need it in python
@@OlexaYT oh alright, I thought the game code required it. Thanks for the reply, great video
PUMKPIN ISSUE:
1) insuffiecient pumkin seeds
2) Coord_list
1): move while not trade_req... out of the for loop. you know for this for loop you need at most get_world_size()**2 seeds (therefore you dont reset the grid in the middle of planting seeds
2) append to coord_list both non seeded fields and pumpkins still growing!!! therefor you will check those fields in your next loop still.
if (get_entity_type() != Entities.Pumpkin OR not can_harvest()):
#either there is no pumpkin below me or there is a pumpkin but i cannot harvest it yet:
temp_coord.append(coord)
or of course !(A and B) = (!A or !B)
if not (get_entitiy_type() = Entitites.Pumpkin AND can_harvets()):
#there is not a pumpkin that i can harvest below me:
temp_coord.append(coord)
therefore it is better to do a while loop checking if your coord_list is empty, not going over the coord_list list only once.
so right at the start, append every field you are currently sitting on that is not a FULLY GROWN pumpkin (so not harvestable AND not get_entity_type(E.pumpkins) )
for the first round you can start with an empty list, do your for x y loop and append all fields, then you do a while not empty list and delete the field you now found a fully grown pumpkin when checking
Chsck xy, store xy, move, check nx ny, compare new x,y with old xy, did move (yes stores new xy/no move diffeent direct)
Thanks for getting me addicted to this game! It feels just like programming: I’m up until 1 AM trying to figure out why it runs well, but not aesthetically.
Luckily, I fixed the bug! XD
thats what i have been saying
Next episode when?
isn't a dictionary {0:North, 1:East...} almost the same thing as a list? [North, East, ...]
Definitely, just made sense in my head to have it as key value pairs
Did this series end?
Series never truly end do they?
Deep
Just an idea for the maze, you can have the drone move and when it checks the same way it came you can get it to read the output log and see if the message in there contains the direction they came from. Meaning if it went south it would scan the code for "North" and pass if it scanned it. Also might need to see if you can clear the output log