i'd say try the "cut to different character", and see what you think. implement just one, then play it. does it work? does it not? is it better? is it worse? this is the R&D phase of game development - rapid prototyping.
if you suspect it will be better - it usually turns out to be so.
the open and closed lists are static arrays of structs allocated on the stack (IE local variables).
the number of open and closed nodes in each list is tracked.
init_astar_lists is simply setting num_open_nodes and num_closed_nodes to zero.
the lists use insert at end, and swap and dec count to remove.
the open list stores both x,z, and an id=z*collsion_map_size+x
the main function is:
get_lowest_open does a simple for loop search of the open list array for the index with lowest f
in expand_neighbors i unrolled the nested for loops into eight explicit calls to expand_neighbor.
in expand_neighbor i combined the atomic operations such as add, remove, membership check, etc.
i left in the check for neighbor off edge of collision map, as opposed to using a border of closed nodes. it seemed to me that a border of closed nodes would increase the size of the closed list and therefore slow down membership tests. but this is only due to my implementation method. for some other method with faster membership tests, a border of closed nodes may be faster.
so expand_neighbor ended up looking like this:
if off_edge return
if in_closed_and_not_removed return
if in_open_and_not_removed return
in_closed_and_not_removed does the membership test. if the test succeeds and the node should be removed, it does the remove. it then returns a result, saying what it did.
in_open_and_not_removed works in a similar manner.
ints are used for f, g, and h, and h is just BBox distance to goal. i tried floats and sqrt(2) for diagonal cost and true 2d distance, its just slower.
the parents are stored in a 2d array the same size and scale as the collision map. and there's no need to initialize it.
extract_path pulls the path from the 2d array and stores it in a 1D path array, which is then copied to the entity's path array. it could be modified to extract directly to an entity's path.
the collision map system was modified to handle collision maps at arbitrary scales. collision maps are now generated at different scales, based on the diameter of the critter in question. so critters are always one square in size. obstacle radii are grown by 1 to account for critter radius when going around corners.
Astar uses the collision maps for passable/impassable node checks.
before astar actually runs, it does a number of checks:
1. if the start is in impassable terrain, it finds the closest open node and does LOS movement to there. this check may be unnecessary.
2. if the goal is in impassable, it finds the closest open node to the goal and does Astar movement to there. this can occur if the goal is a critter who seems to be in impassable terrain due to the collision map scale vs their size. IE a human of diameter 2 can move to what appears to be inside a rock on a collision map at a scale of 6.
3. it then gets the goal for the current collision map, based on the ultimate goal. this is basically a raycast to the edge, followed by an outwardly expanding edge search for open nodes on both this map's edge, and the adjacent map's edge. if the ultimate goal is in the current collision map, it simply returns the ultimate goal as the current goal.
4. if it can not find an open edge node for the current goal, it tries LOS. this case will only occur if the entire edge of a collision map is impassable. IE its ocean or impassable mountains. in such cases you're more or less screwed anyway. i mean if your target takes off on a raft across the ocean, there's not much you can do about it. especially if you're an animal that can't build a raft and give chase.
5. if the start == the current goal, either its at the ultimate goal or at the edge of a collision map, either way LOS is used to get the rest of the way, or to the next collision map.
if none of the above conditions is true, it runs astar out to a range of 50 feet. this is far enough to get the critter moving in the correct direction around large obstacles, even if it doesn't path all the way past them.
when following the path, if they are more than one node distant from node zero, they goto node zero, else they goto node 1.
optimization of real-time collision map generation at arbitrary scales may be called for.
further optimization of astar itself may be called for with a large number of active critters at once.
i'm currently running A* every update, which is probably unnecessary. it should only have to be run when the goal changes, or when they exhaust the nodes in their current path, or when they deviate drastically from the path for some reason.
1. don't forget that extracted paths are in reverse order.
2. collision maps at arbitrary scales meant i was dealing with three coordinate systems: world, collision map, and scaled collision map. this led to a bit of confusion as different parts used different coordinate systems. in the end i converted everything from world to scaled collision map coordinates, did all the astar stuff, then converted the results back to world coordinates.
3. i was quite surprised how just a few things like insert-at-end, swap and dec, unrolling the loops in expand neighbors, and especially combining the atomic calls in expand neighbor really made a big difference in performance. all my times are zero milliseconds now. i'm down to having to measure astar execution time in clock ticks.
>> Strongly disagree, on what experience do you base that assumption?
that you don't model such a large number of stars that you have to partition space to check collisions.
have you tried it yet? at what point (how many stars with how many planets per star on average and how many moons per planet on average) is an oct-tree required? would it apply to my case of 1000 stars with 10 planets and 10 moons per? or can i go 100,000 stars? or 100,000,000? when do i hit oct-tree requirements? if you haven't tried it, it would seem to me to be pre-mature optimization.
>> there is problem of people paying low salary to evade tax and send rest.
that's not a problem - that's real life. IE its part of the system you are trying to model.
McDonald's and such employ part-timers because its less taxes and benefits they have to pay.
you might simplify things by simply making all people and corporate entities separate financial entities that pay taxes on their income. personal property taxes for individuals would be an additional level of detail you could implement at your option. as you say, sales tax is rather straight forward. sales tax on imports / exports are usually uncommon for individual sales. import and export tariffs are another matter though.
>> for example they put an offer of 1000 USD = 0.01 gold themselves while exchange rate was 10 USD then bought that gold from their company account to transfer money freely
if you tax everything on its income, no matter how that income was gained, this should not be an issue.
>> I spent ages trying to get this through to people some years back.
its yet another case of cart before the horse thinking. algos lead to patterns, patterns are not algos.
i was blessed in that i got into games before OO, patterns etc. so i was able to apply the litmus test to each tech as it came down the pike: "so just what does this do for game development?".
i didn't have the cognitive baggage of "this how its should be done" that one seems to get from a modern C++ course of study for non-game development.
and the really sad fact is that aside from graphics cards, DX and OGL, by and large the rest of the computing world still doesn't give a damn about gamedevs. OO was not designed specifically for games. neither were patterns. i saw some guy is doing a game patterns book. most of the patterns listed seemed patently obvious. i chalked it up to yet anther person writing a book in an attempt to cash in on the game development scene. there have been so many over the years.
1. determine the types of game(s) to be supported.
2. determine the team size to be supported. IE one person with full code access, vs a large team with non-coders. large teams with non-coders will require additional tools / systems not required by the lone wolf.
3. determine the systems common to all game types supported (timers, mesh and texture memory pools, low level graphics and audio engines, etc.)
4. implement the common subsystems identified in step 3.
5. determine game specific systems required for the game types supported. influence maps for an RTS might be an example. or an inventory system for a RPG. or heightmaps and terrain chunks for a land based game. or local rotations for a flight sim.
6. implement the game-type specific systems identified in step 5.
7. determine what editors, import or conversion tools, etc are required to complete the development pipeline.
8. implement the additional tools identified in step 7.
9. test implement games with the engine to integration test all engine systems.
10. modify the game engine as needed based on the results of step 9.
11. repeat steps 9 and 10 until the engine is v1.0 "gone gold" quality.
i think that about covers it. i may have forgotten a step or two though.
the .x file format specification can be found in the june 2010 DX SDK download. from that you can simply read the .x file manually to determine if its correct with respect to the bones (frames) in question.
if it is correct, having now looked at the file, odds are you'll see where you are parsing incorrectly.
me personally, i'd probably just use the DX API calls to load the model into a mesh (and controller), then just copy out the data needed, and release the model and controller. no need to get into parsing complex file formats. parsing code's already been written, all you need is the data.
>> I was thinking that if we can use Octrees for collision detection, frustum culling and raytracing, why can't we use this beautiful data
structure to solve the universe rendering problem.
odds are an octree is overkill for both collisions and culling.
not subdividing space would probably be simpler.
what you want to do is similar to what SIMSpace v8.0 already does. the only real difference being SIMSpace uses a generic skybox and only renders nearby bodies. in your case, you'd just clear the screen to black (or whatever) then draw as many stars as you could see, and had time to draw. same idea as drawing stars in SIMSpace, but you draw stars beyond a certain range as just a pixel, with color determined by star color and brightness determined by range.
SIMspace uses a world coordinate system of quadrants, sectors, and meters. quadrants and sectors are stored in ints, and meters is stored in a float. 1 sector is 1 million meters across, and a quadrant is 1 million sectors across. so the coordinate system can go up to about +/-4 trillion quadrants or -4E24 though 4E24 meters. that about 845 million light years across.
the game itself uses a space large enough to hold 1000 stars at the same average density as the milky way galaxy. which works out to a cube 14E17 meters across.
for drawing, simply divide range and scale by a constant, and lerp scale from the divided scale to zero as range goes from collision range to max visual range. max visual range is defined as the range at which you no longer bother drawing. i'm using 100 times diameter as visual range for an object. in your case, visual range is where you stop drawing a sphere mesh and start drawing a pixel. so instead of drawing a sphere, you draw just one pixel at one color and one depth. and just like that, boom, you have realtime rendering of your stars database.
for the initial testing of the system, i used a star the size of the sun, and divide its size and scale by 100 million. the result is a unit sphere of about scale 7 drawn at ranges from 7 to 1400 d3d units. all of which is quite doable with just floats.
>> I was reading about the factory pattern and became confused as to when to apply them.
you do that with algos, not patterns.
folks seem to miss that bit. algos are implementation methods that often have best use cases associated with them (IE its generally known when and where they perform well and poorly). algos are what you consider and choose from for code implementation. technically speaking, patterns are a generic way to describe the solution post mortem, nothing more. due to the fact that a pattern can be similar to an algo, folks sometimes treat patterns as algos. and worse yet, they think they are the only algos, or somehow superior. when in actuality they are recurring patterns of code organization commonly found in non-realtime business apps. which is probably one strike against them right out of the gate when considering them for realtime game use. non-realtime business apps have little in common with realtime modeling and simulation software (IE games). take a look at the projects the "new gang of four" looked at when writing their design patterns book. any of them games? No? didn't think so.
so the question should be "is this algo (not pattern) required?"
given that main() is the only thing required, the obvious answer is no.
so the question really should be "whats the best algo to do this?"
figure that out, implement it, then see what pattern it looks like. that's how you determine "what pattern to use". odds are a proper implementation will be a "game pattern" not a business app pattern, or it will be a design principle that already existed that they have renamed for their book (such as flyweight, SRP, etc. all very standard design stuff that's been around a lot longer than c++).
i use a c++ compiler for the stronger compile time checking, but the code is largely C. if i want to use C++ syntax i can. if i don't, i don't have to. so if i need polymorphism, inheritance, lambdas, etc, they are available. but 99% of the time, plain old C without the sugar coated wrapper of C++ syntax works just fine, and is usually less typing.
in general when you ask this type of question you'll get two types of responses, those from folks who only know c++ (younger programmers), and those who know there were games before C++ existed (older programmers).
i wrote my first PC game in 1982. so i'm definitely in the "games came before c++" group. 99% of the original purpose of c++ syntax was to make extending existing code bases easier. unfortunately, extending exiting code bases is something that's rarely required in games. but of course, if you've got a new hammer, you've just got to frickin' use it. so wait! we can also use it as a design methodoloy! but again, unfortunately non-trivial games are about performance, not academic design methodologies / methods of source code organization. those raised on C++ alone are usually unaware of the original purpose behind c++ syntax, and the history of the rise of OO design methodology.
this also speaks to the continual trend of hardware and software manufacturers coming out with new stuff (other than graphics cards), but not directly targeting games. and then feeling left out, gamedevs try to find a way to use the new tech. or non-gamedevs espouse the tech as a game solution (anyone remember MMX instructions?). in many such cases the fit between games and tech is forced or kludged or only works up to a certain point.
you might try thinking of DoD as designing data structures based on the hardware, and OOP as a way to organize code. as you can see those two things are not mutually exclusive. DoD is an optimization method. OOP is a coding style. and the performance hit of OO vs procedural code is negligible. new() and dispose() are what kill. so you don't new or dispose during runtime (at least not a lot). instead you allocate everything, run, then release everything. mobile development limitations (from what i hear) appear to be more related to lack of ram and high battery consumption rates due to graphic scene complexity.