Simultaneous turn doesn't need any of that. I've seen systems where you just input all your moves simultaneous to your opponent, and then when everyone's done, they all execute at the same time without intervention.
Simultaneous turn doesn't need any of that. I've seen systems where you just input all your moves simultaneous to your opponent, and then when everyone's done, they all execute at the same time without intervention.
Sure. But there are too many questions you have to answer about conflicts.
What if there is a straight road. Two units stand with one empty space between them. Both players give the order to move forward into that space and fire on the opposing unit. They both can't occupy that one space simultaneously, or can they? If they can't, which unit gets to move forward into the space and which one stays still? How do you make the results of these sort of conflicts obvious to the players so nobody is left angry that they ordered to move forward, but the opponent got to move forward instead?
And that's just the simplest possible example. It says nothing about two units emerging from fog of war that both want to end on the same square. Two units with large movement ranges that cross paths.
The other issue is overextending resources. In Advance Wars, even though you take turns, you still fully resolve each unit's orders one at a time. The enemy has an infantry. You attack it with your infantry, it's still alive. You attack it with a tank, now it's dead. You don't attack it again, because it's gone.
With simultaneous turns, even with the simplest case of a completely stationary enemy unit, how many units do you order to attack it? You fire an artillery and have a tank attack it, and have a mech shoot it. Oh, but it would have died from just the artillery, but you didn't know that. You could have had those other units shoot something else and not waste ammo. The reverse is also a problem. Yeah, this mech should be able to finish that off. I'll send my other units elsewhere. Oh crap, it didn't die.
While you could potentially make a good game with completely simultaneous turns, you will have to answer these difficult questions, and many more. If you make the game real-time OR make each unit's orders fully resolve one at a time, all of these problems just go away.
If I were making that game, I'd focus the "war engine" on things like attacks of opportunity, zones of control, and the effects of maneuver.
Say, a stationary tank has a wide range of dangerous zone control (attacks of opportunity and limiting of enemy unit movement through). But, a slowly moving tank has a narrower zone of control/interaction along its path, and a fast moving tank has zero zone control but forward offensive characteristics.
Stuff like that.
The game is:
1. Set up your turn 2. Watch how the bullshit all plays out when troops do unexpected things in the face of heavy fire
Watching it unfold based on your orders is the value to the player. The milsim grognards love to explore how and why things happen. Let them order a bunch of infantry and panzer divisions around, and then step back and watch it play out? They'll come.
I already referenced that for most of my hex board implementation. Cubic coordinates are awesome. However, it's not very useful for actual game mechanics.
Some of the big pages are really slow, and my caching thing is fucking up due to character encoding issues I don't have time to fix now (why the fuck standards if standards aren't gaaaaaugh?). I'll get through and optimize those pages to store more stuff in the database and not have to do so much number crunching on each request.
Now it's going to be way easier to add functionality to the website, so I can do some deeper dives into the data. Like player head to heads: http://fightnightcombat.com/headtohead-1-2.html
Ah. Yeah. About that. I wanted to put posts from my wordpress blog, which is on the same server, on the front page. I faffed around for a while, and in the end sticking .php at the end to make sure the browser did the right thing was the least faffy way I could get it to work at all.
Now I've just noticed that if you go to just http://fightnightcombat.com/ it is serving it as a html file. So the blog post part is broken. Which it wasn't on the dev server. Damn.
Anyway, my next new job is to be bring the news posts into the Django system, so to better and more easily link the news stories with events and players. That way each player profile and every tournament page can display links to or excerpts of every news story that mentions that player/tournament. Soon the whole php/wordpress issue will go away.
Well, I didn't get through Round 1A, which was a bit disappointing (1156th). Mostly I was just a bit too slow; I spent too much time thinking about a properly efficient solution for B when I had already very quickly come up with one that was good enough.
OK, I got a far better result in Round 1B (114th), so I'm through to Round 2 of Google Code Jam now.
Looking good! I have a small-ish project I'm fantasizing about in Unity that I will hopefully take off on once my Chewbacca suit is done for Connecticon.
Agree that idle animations are a huge deal that add a lot to the visuals.
Working on a project for a class, but there's always a moment when I'm coding Python where the ability to do something will shock me, just because it makes so much sense, or makes code more readable, or is just cool. I was shocked that this was a valid construction in Python:
article_list = [link.get('href') for link in soup.find_all('a')]
Man I am struggling with my Data Structures and Algorithms teacher. He sets a project to write a data structure to act like a Dictionary class in Java. So I started an AVL tree. The he made the amendment that all functions had to run in O(log n) and memory was also a concern. So I started rewriting it to a Red Black Tree. Today he amended it to state that the only way you could be in HD range is if it ran in time complexity O(log log n) and I can't use any of the default Java library not sure how the rest of the students are going as the majority don't know how to make something comparable.
Now I'm looking up all these experimental data structures which have special conditions. The wastage of my time is real.
Yeah when I did that the first time I was amazed by my one line power when compared to what I needed to do in Java to do the same thing. Add a lambda function and watch your mind get blown.
We use anonymous functions at work for things like our Retry class ("the hammer"). Give it a function, a maximum count, and an array of acceptable exception types. It will proceed to hammer it for you. Useful for smoothing over dumb things we do all the time, like dealing with FTP connections that time out.
Man I am struggling with my Data Structures and Algorithms teacher. He sets a project to write a data structure to act like a Dictionary class in Java. So I started an AVL tree. The he made the amendment that all functions had to run in O(log n) and memory was also a concern. So I started rewriting it to a Red Black Tree. Today he amended it to state that the only way you could be in HD range is if it ran in time complexity O(log log n) and I can't use any of the default Java library not sure how the rest of the students are going as the majority don't know how to make something comparable.
Now I'm looking up all these experimental data structures which have special conditions. The wastage of my time is real.
You haven't stated the answers to some important questions: - What type are your dictionary keys (or, for generic types, what functions / interfaces are present)? What restrictions apply to your inputs, if any? - Do you mean worst-case time complexity, or average-case? I'd assume it's the former because it's the usual interpretation, but if it's the latter then the exercise is much easier.
Also, I don't get why you would switch from an AVL tree to a red-black tree for the reasons you gave; both are O(log n) anyway, and neither of them has significant memory overhead.
Yeah doing an AVL tree should be fine. You would always ensure O(log n) runtime and O(n) space, which you can't really get better than for collections.
As far as anonymous functions usually things that will result in a method of one line and get passed as a callback or something I'll use anonymous functions. For instance a lot of LINQ functions in .NET take comparator functions to determine selection. If I have a few in a class I'm not gonna make a bunch of random one off methods to support those.
Similarly certain callbacks like assignments from an Ajax call in JavaScript I don't really need to define a named function to manage that callback. Doing it inline is fine enough and usually easier to read. Although in JavaScript functions are kinda funky objects.
Oh I didn't realize you need to get O(log log n) to get a higher grade. You basically want something like this. More specifically because you are doing a dictionary.
Whoops, should have probably checked the forums rather than beat my head against my keyboard trying to write a top down implementation of Delete on a Red Black tree.
Lackofcheese was correct in that these times are all worst case.
Half the problem is the assignment being poorly worded. I'm essentially getting the notion that he wants something like a Map or Set functionality that works in log log N time. Probably the most frustrating thin I've done.
I will try to switch to an AVL tree if I can't get the Red Black to work in the next hour or so and be happy with the mid range mark as I have 2 more projects at the moment, if I finish the other two early I'll try and implement a novel approach.
Fail of my weekend coding: Programming competition, team did not listen to me that a DFS would give us a linear time solution on finding cycles, and continued to try and implement a super modified BFS. Then one of them revealed that they had full notes and pseudo for both with him but did not pull them out till he got a hold of the keyboard. Also Java sucks as a competitive programming language. Scanner and BufferReader were taking 29 and 10 seconds to to read the inputs for a problem for which we had coded a super efficient solution. The same solution in C++ was completing in under 2 seconds. Should be fine to compete in C next semester.
Without additional information / constraints, I don't think it's even possible to do better than log(N).
Presumably there is some kind of specification that says that your key types have to be comparable (less / greater / equal); did that specification tell you anything else?
If it was possible for your data structure to work in O(log log N) time for insertion and searching operations, you could use it to achieve an O(N log log N) comparison sort. That, however, simply isn't possible in the general case.
Incidentally, getLogString() looks like a minor trap to me.
Comments
What if there is a straight road. Two units stand with one empty space between them. Both players give the order to move forward into that space and fire on the opposing unit. They both can't occupy that one space simultaneously, or can they? If they can't, which unit gets to move forward into the space and which one stays still? How do you make the results of these sort of conflicts obvious to the players so nobody is left angry that they ordered to move forward, but the opponent got to move forward instead?
And that's just the simplest possible example. It says nothing about two units emerging from fog of war that both want to end on the same square. Two units with large movement ranges that cross paths.
The other issue is overextending resources. In Advance Wars, even though you take turns, you still fully resolve each unit's orders one at a time. The enemy has an infantry. You attack it with your infantry, it's still alive. You attack it with a tank, now it's dead. You don't attack it again, because it's gone.
With simultaneous turns, even with the simplest case of a completely stationary enemy unit, how many units do you order to attack it? You fire an artillery and have a tank attack it, and have a mech shoot it. Oh, but it would have died from just the artillery, but you didn't know that. You could have had those other units shoot something else and not waste ammo. The reverse is also a problem. Yeah, this mech should be able to finish that off. I'll send my other units elsewhere. Oh crap, it didn't die.
While you could potentially make a good game with completely simultaneous turns, you will have to answer these difficult questions, and many more. If you make the game real-time OR make each unit's orders fully resolve one at a time, all of these problems just go away.
If two units move into eachother, BAM! Frontal combat as though they'd attacked eachother.
Say, a stationary tank has a wide range of dangerous zone control (attacks of opportunity and limiting of enemy unit movement through). But, a slowly moving tank has a narrower zone of control/interaction along its path, and a fast moving tank has zero zone control but forward offensive characteristics.
Stuff like that.
The game is:
1. Set up your turn
2. Watch how the bullshit all plays out when troops do unexpected things in the face of heavy fire
Watching it unfold based on your orders is the value to the player. The milsim grognards love to explore how and why things happen. Let them order a bunch of infantry and panzer divisions around, and then step back and watch it play out? They'll come.
Some of the big pages are really slow, and my caching thing is fucking up due to character encoding issues I don't have time to fix now (why the fuck standards if standards aren't gaaaaaugh?). I'll get through and optimize those pages to store more stuff in the database and not have to do so much number crunching on each request.
Now it's going to be way easier to add functionality to the website, so I can do some deeper dives into the data. Like player head to heads: http://fightnightcombat.com/headtohead-1-2.html
Now I've just noticed that if you go to just http://fightnightcombat.com/ it is serving it as a html file. So the blog post part is broken. Which it wasn't on the dev server. Damn.
Anyway, my next new job is to be bring the news posts into the Django system, so to better and more easily link the news stories with events and players. That way each player profile and every tournament page can display links to or excerpts of every news story that mentions that player/tournament. Soon the whole php/wordpress issue will go away.
This week I implemented:
Agree that idle animations are a huge deal that add a lot to the visuals.
article_list = [link.get('href') for link in soup.find_all('a')]
So I started an AVL tree.
The he made the amendment that all functions had to run in O(log n) and memory was also a concern.
So I started rewriting it to a Red Black Tree.
Today he amended it to state that the only way you could be in HD range is if it ran in time complexity O(log log n) and I can't use any of the default Java library not sure how the rest of the students are going as the majority don't know how to make something comparable.
Now I'm looking up all these experimental data structures which have special conditions.
The wastage of my time is real. Yeah when I did that the first time I was amazed by my one line power when compared to what I needed to do in Java to do the same thing. Add a lambda function and watch your mind get blown.
- What type are your dictionary keys (or, for generic types, what functions / interfaces are present)? What restrictions apply to your inputs, if any?
- Do you mean worst-case time complexity, or average-case? I'd assume it's the former because it's the usual interpretation, but if it's the latter then the exercise is much easier.
Also, I don't get why you would switch from an AVL tree to a red-black tree for the reasons you gave; both are O(log n) anyway, and neither of them has significant memory overhead.
As far as anonymous functions usually things that will result in a method of one line and get passed as a callback or something I'll use anonymous functions. For instance a lot of LINQ functions in .NET take comparator functions to determine selection. If I have a few in a class I'm not gonna make a bunch of random one off methods to support those.
Similarly certain callbacks like assignments from an Ajax call in JavaScript I don't really need to define a named function to manage that callback. Doing it inline is fine enough and usually easier to read. Although in JavaScript functions are kinda funky objects.
Lackofcheese was correct in that these times are all worst case.
Half the problem is the assignment being poorly worded. I'm essentially getting the notion that he wants something like a Map or Set functionality that works in log log N time. Probably the most frustrating thin I've done.
I will try to switch to an AVL tree if I can't get the Red Black to work in the next hour or so and be happy with the mid range mark as I have 2 more projects at the moment, if I finish the other two early I'll try and implement a novel approach.
Fail of my weekend coding: Programming competition, team did not listen to me that a DFS would give us a linear time solution on finding cycles, and continued to try and implement a super modified BFS. Then one of them revealed that they had full notes and pseudo for both with him but did not pull them out till he got a hold of the keyboard. Also Java sucks as a competitive programming language. Scanner and BufferReader were taking 29 and 10 seconds to to read the inputs for a problem for which we had coded a super efficient solution. The same solution in C++ was completing in under 2 seconds. Should be fine to compete in C next semester.
Presumably there is some kind of specification that says that your key types have to be comparable (less / greater / equal); did that specification tell you anything else?
If it was possible for your data structure to work in O(log log N) time for insertion and searching operations, you could use it to achieve an O(N log log N) comparison sort. That, however, simply isn't possible in the general case.
Incidentally, getLogString() looks like a minor trap to me.