• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.


  • Content count

  • Joined

  • Last visited

Community Reputation

548 Good

About Zouflain

  • Rank
  1. Shards are isolated sets of data. When I create my character DudeGuy19192 on Shard 1 and then and you create your character DudeGuy19192 on Shard 2, nobody gets a "name already used" message because each Shard is basically the entire game in isolation.   Blades are allocations of hardware resources, typically on games with single sharded architectures. If 100,000 players are in one zone, the work of computing that zone will be shared by multiple blades (processors). The rest of the zones might all be shunted to one blade, with all of the others working tirelessly to support that one mega-zone. Jita comes to mind when talking about Eve...   Zones are collections of data within a shard. Typically this data is just "there is a monster here with n hitpoints at (x,y) coordinates." They rarely if ever hold account data (that's what Shards do). Instances are typically implemented as zones.   Rooms and scenes are the same thing, even smaller collections of data if they are used at all. When you enter a door, but don't have to load into it, it means you're probably still in the same zone but possibly a different room. It can be useful for grouping objects (no need to collision check things in room 1 with things in room 2), but I rarely see them used any more. It's easy to just teleport you to some unreachable spot in the zone and not deal with this layer.   Worlds are equivalent to Shards. So are "Servers."
  2. Sorry about the missing attachment.   So I tried simplifying the problem by reducing the number of input points and watching it build systematically. I've spotted the first step where a problem occurs (see example2). I'm still stumped as to [i]why[/i] this is the case, but at least I know where it's happening.      
  3. I'm more rusty than I care to admit, both in the math and programming department. Coming back from a very long hiatus, I'm having serious trouble identifying my mistake in implementing the Bowyer-Watson algorithm. To describe the issue, I'd have to say that somewhere along the line the wrong edges are being removed from the triangulation (aka "std::list<Triangle> triangles") and I cannot figure out why. In the attached example.png I highlighted two problem areas: in red you see an edge that clearly should not exist, and in mauve you see a point that ought to have edges but doesn't. The greenish lines are the remaining edges and the rectangles are centered about the points fed into the bowyers watson algorithm. I tried to follow the algorithm as tightly as possible. Anyone willing to point me in the right direction would be greatly appreciated. I've been analyzing and reanalyzing line by line for 3 straight days to figure out what the problem is to no avail. The code is below. I've tried to keep it as clean and readable as possible, but the algorithm is verbose. Most of it is boiler plate. The last function is the actual algorithm. I've included the boiler plate just in case the error is there. Delaunay.hpp #ifndef DELAUNAY_HPP #define DELAUNAY_HPP #include "types.hpp" #include <list> namespace Delaunay{ struct Point; struct Triangle; struct Edge; typedef std::list<Point> PointList; typedef std::list<Triangle> TriangleList; typedef std::list<Edge> EdgeList; struct Mat3i{ S64 matrix[9];//COLUMN MAJOR order inline S64 determinant(void) const{ return matrix[0]*(matrix[4]*matrix[8]-matrix[7]*matrix[5]) -matrix[3]*(matrix[1]*matrix[8]-matrix[7]*matrix[2]) +matrix[6]*(matrix[1]*matrix[5]-matrix[4]*matrix[2]); } inline S64& operator[](int n) { return matrix[n]; } Mat3i(S64 i_x,S64 j_x,S64 k_x,S64 i_y,S64 j_y,S64 k_y,S64 i_z,S64 j_z,S64 k_z);//ROW MAJOR input, for easy reading }; struct Mat4i{ S64 matrix[16];//COLUMN MAJOR order inline S64& operator[](int n) { return matrix[n]; } S64 determinant(void) const; Mat4i(S64 i_x,S64 j_x,S64 k_x,S64 l_x,S64 i_y,S64 j_y,S64 k_y,S64 l_y, S64 i_z,S64 j_z,S64 k_z,S64 l_z,S64 i_w,S64 j_w,S64 k_w,S64 l_w );//ROW MAJOR input }; struct Point{ S32 x,y,room_id; Point& operator=(const Point& point); inline bool operator==(const Point& point) const{ return(x==point.x&&y==point.y); } inline bool operator!=(const Point& point) const { return !(*this == point); } Point(const Point& point); Point(S32 x=0,S32 y=0,S32 room_id=-1); }; struct Edge{ Point points[2]; inline bool hasPoint(const Point& point) const{ return points[0]==point||points[1]==point; } Edge& operator=(const Edge& edge); inline bool operator==(const Edge& edge) const{ return hasPoint(edge.points[0])&&hasPoint(edge.points[1])&&points[0]!=points[1]; } Edge(const Edge& edge); Edge(const Point& p1=Point(),const Point& p2=Point()); }; struct Triangle{ Point points[3];//ALWAYS in counter clockwise order (after initialization) inline bool hasEdge(const Edge& edge) const{ return Edge(points[0],points[1])==edge||Edge(points[1],points[2])==edge||Edge(points[2],points[0])==edge; } inline bool hasPoint(const Point& point) const{ return points[0]==point||points[1]==point||points[2]==point; } inline bool sharesPoint(const Triangle& triangle) const{ return hasPoint(triangle.points[0])||hasPoint(triangle.points[1])||hasPoint(triangle.points[2]); } bool circumcircles(const Point& p) const; void makeCounterClockwise(void);//used in each initialization path, keeps points in CCW order Triangle& operator=(const Triangle& triangle); inline bool operator==(const Triangle& triangle) const{ return sharesPoint(triangle.points[0])&&sharesPoint(triangle.points[1])&&sharesPoint(triangle.points[2]); } inline bool operator!=(const Triangle& triangle) const{ return !(*this==triangle); } Triangle(const Triangle& triangle); Triangle(const Point& p1=Point(),const Point& p2=Point(),const Point& p3=Point()); Triangle(const Point& point,const Edge& edge); }; EdgeList bowyerWatson(const PointList& points); } #endif Delaunay.cpp #include "delaunay.hpp" #include <cstdio> using namespace Delaunay; Delaunay::Mat3i::Mat3i(S64 i_x,S64 j_x,S64 k_x,S64 i_y,S64 j_y,S64 k_y,S64 i_z,S64 j_z,S64 k_z){ //Again this is ROW MAJOR input, COLUMN MAJOR storage matrix[0]=i_x;matrix[3]=j_x;matrix[6]=k_x; matrix[1]=i_y;matrix[4]=j_y;matrix[7]=k_y; matrix[2]=i_z;matrix[5]=j_z;matrix[8]=k_z; } S64 Delaunay::Mat4i::determinant(void) const{ Mat3i a( matrix[5],matrix[9],matrix[13], matrix[6],matrix[10],matrix[14], matrix[7],matrix[11],matrix[15]), b( matrix[1],matrix[9],matrix[13], matrix[2],matrix[10],matrix[14], matrix[3],matrix[11],matrix[15]), c( matrix[1],matrix[5],matrix[13], matrix[2],matrix[6],matrix[14], matrix[3],matrix[7],matrix[15]), d( matrix[1],matrix[5],matrix[9], matrix[2],matrix[6],matrix[10], matrix[3],matrix[7],matrix[11]); return matrix[0]*a.determinant()-matrix[4]*b.determinant()+matrix[8]*c.determinant()-matrix[12]*d.determinant(); } Delaunay::Mat4i::Mat4i(S64 i_x,S64 j_x,S64 k_x,S64 l_x,S64 i_y,S64 j_y,S64 k_y,S64 l_y, S64 i_z,S64 j_z,S64 k_z,S64 l_z,S64 i_w,S64 j_w,S64 k_w,S64 l_w){ //ROW MAJOR input, like mat3 matrix[0]=i_x; matrix[4]=j_x; matrix[8]=k_x; matrix[12]=l_x; matrix[1]=i_y; matrix[5]=j_y; matrix[9]=k_y; matrix[13]=l_y; matrix[2]=i_z; matrix[6]=j_z; matrix[10]=k_z; matrix[14]=l_z; matrix[3]=i_w; matrix[7]=j_w; matrix[11]=k_w; matrix[15]=l_w; } Point& Delaunay::Point::operator=(const Point& point){ room_id = point.room_id; x = point.x; y = point.y; return *this; } Delaunay::Point::Point(const Point& point){ x = point.x; y = point.y; room_id = point.room_id; } Delaunay::Point::Point(S32 x,S32 y,S32 room_id){ this->x = x; this->y = y; this->room_id = room_id; } Edge& Delaunay::Edge::operator=(const Edge& edge){ points[0] = edge.points[0]; points[1] = edge.points[1]; return *this; } Delaunay::Edge::Edge(const Edge& edge){ points[0] = edge.points[0]; points[1] = edge.points[1]; } Delaunay::Edge::Edge(const Point& p1,const Point& p2){ points[0] = p1; points[1] = p2; } bool Delaunay::Triangle::circumcircles(const Point& p) const{ Mat3i geometric_construction( points[0].x-p.x,points[0].y-p.y,(points[0].x*points[0].x-p.x*p.x)+(points[0].y*points[0].y+p.y*p.y), points[1].x-p.x,points[1].y-p.y,(points[1].x*points[1].x-p.x*p.x)+(points[1].y*points[1].y+p.y*p.y), points[2].x-p.x,points[2].y-p.y,(points[2].x*points[2].x-p.x*p.x)+(points[2].y*points[2].y+p.y*p.y) ); return geometric_construction.determinant()>0; }; void Delaunay::Triangle::makeCounterClockwise(void){ //Poor man's vector math S32 vx = points[0].x,vy = points[0].y, ux = points[1].x,uy = points[1].y, wx = points[2].x,wy = points[2].y; S32 vux = vx-ux,vuy = vy-uy, wvx = wx-vx,wvy = wy-vy; //Swap if necessary (dot product > 0) if(vux*wvy-vuy*wvx>0){ Point temp_points[3];//size 3 to make things clear, technically [0] never gets used temp_points[1] = points[2]; temp_points[2] = points[1]; points[1] = temp_points[1]; points[2] = temp_points[2]; } } Triangle& Delaunay::Triangle::operator=(const Triangle& triangle){ points[0] = triangle.points[0]; points[1] = triangle.points[1]; points[2] = triangle.points[2]; return *this; } Delaunay::Triangle::Triangle(const Triangle& triangle){ for(int i=0;i<3;i++){ points[i] = triangle.points[i]; } makeCounterClockwise(); } Delaunay::Triangle::Triangle(const Point& p1,const Point& p2,const Point& p3){ points[0] = p1; points[1] = p2; points[2] = p3; makeCounterClockwise(); } Delaunay::Triangle::Triangle(const Point& point,const Edge& edge){ points[0] = point; points[1] = edge.points[0]; points[2] = edge.points[1]; makeCounterClockwise(); } EdgeList Delaunay::bowyerWatson(const PointList& points){ TriangleList triangles; //add super triangle const int INFINITY = 10000; const Triangle super_triangle(Point(-INFINITY,INFINITY),Point(0,-INFINITY),Point(INFINITY,INFINITY)); triangles.push_back(super_triangle); //add the points incrementally for(auto& point : points){ //Find non-delaunay triangle TriangleList bad_triangles; for(auto& triangle : triangles){ if(triangle.circumcircles(point)) bad_triangles.push_back(triangle); } //Get good edges from bad triangles EdgeList good_edges; for(auto& triangle : bad_triangles){ Edge edges[] = { Edge(triangle.points[0],triangle.points[1]), Edge(triangle.points[1],triangle.points[2]), Edge(triangle.points[2],triangle.points[0]) }; for(auto& edge : edges){ bool keep_edge = true; for(auto& test_triangle : bad_triangles){ if(triangle!=test_triangle && test_triangle.hasEdge(edge)){ keep_edge = false; break;//no need to keep iterating } } if(keep_edge){ good_edges.push_back(edge); } } } //Toss bad triangles for(auto& bad_triangle : bad_triangles){ triangles.remove(bad_triangle); } //Build triangles from good edges for(auto& edge : good_edges){ triangles.push_back(Triangle(point,edge)); } } //Export edges that do not have a point on the super_triangle EdgeList final_edges; for(auto& triangle : triangles){ Edge edges[3] = { Edge(triangle.points[0],triangle.points[1]), Edge(triangle.points[1],triangle.points[2]), Edge(triangle.points[2],triangle.points[0]) }; for(auto& edge : edges){ if(!super_triangle.hasPoint(edge.points[0])&&!super_triangle.hasPoint(edge.points[1])){ final_edges.push_back(edge); } } } return final_edges; } Note: I'll happily supply more info for anyone who's interested in helping. I don't expect anyone to spend too much time wading through somebody else's code, but I included it because I'm not sure what additional information will be needed to find the problem. Thanks again for any pointers.
  4. Eons ago when I did windows programming I used Microsoft's Visual Express, but then I migrated to Linux for a few years and fell in love with GCC and makefiles. It's a much more sensible, portable toolchain than Visual Express and it's hard to give that up. Well I've since started working on a Windows system for various reasons and I'm fighting with MinGW/Msys over environment variables. I have a clear directory for my own includes/libs (namely G:/MinGW/usr/local/) and I can get a project to compile if I export the CPLUS_INCLUDE_PATH and LIBRARY_PATH, but this is an irritating thing to have to repeatedly configure every time I open a MSYS shell. [b]Is there any way to make these environment variables permanent?[/b] I've already tried hardcoding GCC's specs file, but despite following the MinGW instructions, GCC seems to ignore the specs file. I don't really know another workaround.
  5. Not sure how experienced in the language you are, so if this is obvious forgive me, but are you familiar with the difference between a pointer ([i]Sometype* name[/i]) and a reference ([i]Sometype& name[/i]) in C++? It's fairly significant. I could be wrong, but I have [i]never[/i] used or seen references used that way. I suppose it's legal, but you'll have to initialize those references with Object::Object(SomeObject some_value) : some_reference(some_value){}. Is that really what you wanted? Can it never reference nothing (as in nullptr/NULL)?   Also, referencing objects is only necessary for objects that the base object does not own. Ownership is not clear from your post, but say a Box owns 6 Sides, it would probably look more like [source]class Box{     Side top,front,back,bottom,left,right; };[/source] rather than a bunch of pointers to Sides (Side*) or worse references.   If a Train runs on a Railroad, which is presumably shared between many railroads, it might look more like [source] class Train{     Railroad* railroad; };[/source]   Of course, this has its own problems. Raw pointers are easy to get wrong, but c++11 has introduced smart pointers to the stl (and boost has had them for ages)... but that might be a topic for another day. Coupling an object with a hard reference (SomeType&) makes it very hard to check if SomeType is even still around. Scoping also seems like it would become a real pain - and if you're dynamically allocating the memory, why go through the hastle of storing it's location as a reference instead of a pointer?   Then again, I'm no expert. Just chipping in.
  6. Ordinarily, when performing game logic on instances of a generic Entity class, after spacial partitioning and assembling a list of nearby, relevant entities, I would simply toss the list of entities and the relevant entities into a script (usually lua) and do something like: [source] --Below: A wolf hunts for rabbits to eat TYPES = { WOLF=0,RABBIT=1} ... function UpdateEntities(entities_to_update,relevant_entities) for entity in entities_to_update do if GetEntityType(entity)==TYPES.WOLF then DoWolfAi(entity,relevant_entities); end end end ACTIONS = {HUNT=0,FLEE=1,PRAY=1029}; function DoWolfAi(entity,relevant_entities) --Below: look for food local actions = {}; for other in relevant_entities do if other~=entity then if GetEntityType(other)==TYPES.RABBIT then table.insert(a,{action=ACTIONS.HUNT,target=other,priority=GetEntityHunger(entity)*GetDistanceBetween(entity,other)}); end ... end end --Ommited: sort actions by member.priority --Ommited: pick top action (hunt) and do hunt function end [/source] It's pretty straightforward, and works just fine for a small number of instances. In fact, it's served me well for the admitedly hackish projects I've thrown together. But, I'm moving on to larger projects and running into issues of scalability. After getting a massive wakeup call to DoD (Data Oriented Design) and things like cache misses (which didn't matter so much when it was 50 or so objects with simple scripts, but [i]really[/i] matter when it's 100k complex objects), I've come to realize that my old way of doing things is grossly insufficient. The way this handles data seems attrocious, with what I know now. First there's all those "GetBlahBlah(entity)" calls, which usually refer back to an map (std::map or boost::container::flat_map) to fetch data from a generic Entity class. Each one is a lot of overhead, because it has to look up the map to find the Entity, then find Entity.BlahBlah, then pass it all the way back to the script. I shudder to [i]think[/i] what's happening to the cache during all this. That wont work for hundreds or worse thousands of objects. It's also hard to envision a model that works in a cache-friendly manner. Each "wolf" entity needs to fetch data from every nearby "rabbit" entity (namely its location and type), and thus it's dependent on other instances. I also wont know which wolf will need which rabbit when the wolf and rabbit are allocated, so even though flat_map has contiguous memory, I'm forced to use random access rather than sequential (read: cache friendly). My current project has a bit of a challenge mixed in: It has to run decently on a specific machine with an Intel Atom N570 (read: crap). 4 cores, 1.42ghz, ancient technology. That means I have to dance carefully. So, are there any examples of a DoD (Data Oriented Design) approach to the same issue? Every book, every paper, every article I've read uses something more complex but fundamentally similar to the above. From gamedev to gamasutra, very little seems to use Data Oriented Design. I could really use some reference material, or just informative discussion. Thank you. Note: this forum (and only this forum) likes to erase whitspaces and newlines. Not sure why, and it seems unique to me. If it's illegible I appologize, I'll try to edit and fix it but the [i]edits[/i] often times erase [i]more[/i]...
  7. I'm implementing a quadtree for the spacial partitioning of a very large group of objects (target is 400k and trying to get it as fast as I can (target is no more than 50ms for all 400k). My initial naive approach was only able to handle about 1,000 objects in 27 seconds, but I've since been able to get it down to 10,000 objects in 113ms mostly by paying close attention to unnecessary move, copy, and temporary operations. I'm comfortably certain that there are no more such operations that can be eliminated. The quadtree is a structure with two std::unordered_set: the first contains the id#'s of all objects inside the tree node aka "owned" objects, and the second contains the first plus any object close enough to the node's border to be included aka "known" objects. It also has a bounding rectangle defined by its top-left and bottom-right points (can be instantiated Rect(x1,y1,x2,y1) to avoid unecessary Point() constructors). At every update, every known object is inserted into the quadtree. The quadtree is updated with quadtree::insert(const Point&amp;amp;amp; where,const uint64_t&amp;amp;amp; which). --The method checks first if the quadtree has any children AND if it's depth is &amp;amp;lt; a maximum AND if it has &amp;amp;gt; max objecs within it. If that's true, it creates 4 children and dumps both of it's id containers into the children. --The method then checks if it has any children - if so, call quadtree::insert for each child. If not, then check if the bounding rect contains "where" ----If the bounding rect contains "where" insert "which" into both containers ----If not, check if the bounding rect collides with a rect formed around where Rect(where.x-width/2,where.y-width/2,where.x+width/2,where.y+width/2). If so, add it to just the "known" container. Unfortunately, after profiling 10 iterations of 10,000 randomly distributed objects, this leads to about ~408,000 calls to quadtree::insert (~37% execution time), 3,570,000 rect constructors (~6.6%), 7,256,000 point constructors (~10.38%), 3,586,000 stl emplacements (~13.21%). The only really meaningful way to further optimize this that I can see would be to find a less naive way of splitting the quadtree, so that the top node needn't dump every "known" object into every child, which is what is dramatically multiplying the number of constructors. Any advice in this regard would be seriously appreciated. Barely Annotated Code: [source lang="cpp"] bool LogicTree::insert(const QuadPoint&amp;amp; where,const EntityID&amp;amp; which){ bool within = false; //check if split needed if(children.size()==0 &amp;amp;&amp;amp; depth &amp;lt; MAX_DEPTH &amp;amp;&amp;amp; owned.size()&amp;gt;MAX_ENTITIES){ Coord width = bounds.rightBottom.x-bounds.leftTop.x,height = bounds.rightBottom.y-bounds.leftTop.y; QuadRect c1(bounds.leftTop.x,bounds.leftTop.y,bounds.leftTop.x+width/2,bounds.leftTop.y+height/2), c2(bounds.leftTop.x+width/2,bounds.leftTop.y,bounds.leftTop.x+width,bounds.leftTop.y+height/2), c3(bounds.leftTop.x,bounds.leftTop.y+height/2,bounds.leftTop.x+width/2,bounds.leftTop.y+height), c4(bounds.leftTop.x+width/2,bounds.leftTop.y+height/2,bounds.rightBottom.x,bounds.rightBottom.y); children.emplace_back(new LogicTree(c1,depth+1)); children.emplace_back(new LogicTree(c2,depth+1)); children.emplace_back(new LogicTree(c3,depth+1)); children.emplace_back(new LogicTree(c4,depth+1)); for(auto&amp;amp; child : children){ massInsertChild(child); } } //Pass to children or insert if(children.size()&amp;gt;0){ for(auto&amp;amp; child : children){ if(child-&amp;gt;insert(where,which)){ within = true; } } }else{ if(bounds.contains(where)){ owned.emplace(which); known.emplace(which); within = true; }else if(bounds.intersects(QuadRect(where,MAX_RANGE))){ known.emplace(which); } } return within; } [/source]P.S&amp;gt;If this comes out as a solid block of text, my appologies - for some reason this forum likes to delete my newline characters. Edit: Attempt #1 to fix the whitespace nuke. Also fixed a mistake (400k not 3mil, lol).
  8. &nbsp; &nbsp; You're absolutely right. I realized this on the way to work after posting. All persistant values (sans the function definitions) were stored in an SQL database, so there's no reason not to just pre-load the virtual machines with the LUA code. Initializatio might be slow, but it only has to happen once (even though the threads might dynamically open and close, they can simply re-use the already-initialized lua states). Thanks for pointing this out.
  9. I've hit a brick wall when it comes to an algorithm I'm working on. Data objects are distributed on a quad-tree, and each leaf node is batch processed by an OS thread from a threadpool. The actual processing happens in Lua, however, and that's where I run into serious problems. I understand that every OS Thread should have its own lua_State, but initialization of the Lua script is slow: it's a very large, very extensive script split between multiple files with plenty of C functions tied in - parsing and initializing all this again and again would be nightmarishly slow. Instead I'd rather initialize once, copy the read-made data into each thread's lua_State, and then run the processing. Unfortunately, Lua seems to define "thread" as something totally different than an OS thread, and functions like lua_newthread or lua_xmove are only intended for single-threaded applications. It also makes googling about this almost impossible: everything is about co-routines, which I can't see being helpful here. Any advice for moving forward would be greatly appreciated.
  10. Sorry if I wasn't clear, I'll clarify: There is an nxn grid, say: A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 The current brute force algorithm loads A1, B1, A2 and B2 then processes A1. Next, it loads C1 and C2, and processes B1. Next it loads D1,E1,D2, and E2 while unloading A1 and A2, then processes C1. And so fourth. In short, iterate over every member of the grid - load any unloaded neighbors, unload any loaded non-neighbors. My current algorithm takes about 27,000 ms to cover a 512x512 grid. I'd like to get this down. Several orders of magnitude if possible... edit: WHY does this forum delete newlines?!?!?!?!?!?
  11. Thanks for the help! ...but like I said in the PS, this is all one transaction (ie all in one BEGIN/END). Even if it wasn't, that wouldn't explain why sqlite3_exec is faster than sqlite3_step - in both cases, not framing it in a transaction would cause every insert to have its own transaction. I'd appreciate any other ideas, though.
  12. Hello! I'm loading a large batch of objects and I'd like to optimize a bit. The way the load code currently works, it loads each member of an nxn grid and its 8 neighbors (if they aren't loaded already) while also offloading any loaded object that isn't a neighbor. Rather than brute-force with something like (for x in [0,n] do for y in [0, n] do "if not loaded, load index x+y*n and any not loaded neighbors"), I'd rather precompute a sequence of indices that minimizes the number of times any given tile must be loaded, then iterate across it. Since no object can be operated on without its neighbors having been loaded, I must iterate over [i]every[/i] object. What algorithm would produce such a sequence for any given nxn array? I suspect a quad tree would be useful, but there might be simpler ways that I haven't thought of. n in the target case is 512. I'd prefer to assume that each object is very large, and therefore only a minimum of objects should be loaded. Objects are also slow to load/unload, which is why I'd prefer to minimize the "hits." Thanks for any input!
  13. Clearly I'm doing something incorrectly, because the overwhelming consensus is that sqlite3_prepare is considerably faster than sqlite3_exec, but I'm experiencing an extreme bottleneck at the sqlite3_step function. int err; std::string sqlstr = std::string("REPLACE INTO `Entities` VALUES(")+std::to_string(id) +std::string(",")+std::to_string(kind)+std::string(",") +std::to_string(nibble)+std::string(",")+entityStr; err = sqlite3_exec(SQLINTERFACE.getDatabase(),sqlstr.c_str(),nullptr,nullptr,nullptr); //...error checking code...Runs about 50~100x faster than //ST_ENTITY_EXPORT: "REPLACE INTO `Entities` VALUES(?,?,?,?);" sqlite3_stmt* statement = SQLINTERFACE.getStatement(Interface::ST_ENTITY_EXPORT); sqlite3* database = SQLINTERFACE.getDatabase(); err = sqlite3_bind_int64(statement,1,id); genericSQLError(statement,database,err);//error checking code err = sqlite3_bind_int64(statement,2,kind); genericSQLError(statement,database,err); err = sqlite3_bind_int64(statement,3,nibble); genericSQLError(statement,database,err); err = sqlite3_bind_text(statement,4,entityStr.c_str(),entityStr.size(),SQLITE_TRANSIENT); genericSQLError(statement,database,err); err = sqlite3_step(statement); if(err!=SQLITE_DONE){ genericSQLError(statement,database,err); } sqlite3_reset(statement); I've copied it verbatim, so there's a few "blackbox" functons, but they aren't responsible for the slowdown. genericSQLError does not alter parameters, or anything referenced by them - it's a utility function for error checking. The code bottlenecks at sqlite3_step, despite sqlite3_exec recieving a directly equivalent statement. I'd appreciate any help finding a possible cause for the bottleneck. P.S> Yes, all of this is in a transaction.
  14. I think I can say this most succinctly as thus: Given a 128x128 tile grid and a boolean tile mask that describes pathability, what algorithm would you use to generate a "good-looking" (as opposed to "realistic") terrain heightmap? Articles/papers describing these algorithms in a reader-friendly manner would be greatly appreciated.<br> Specifically, I'd appreciate it if the algorithm was stitch friendly (that is, interpolation between two bordering regions, probably by including an "overlap" boundary for merging, produces few noteworthy artifacts both graphically and in terms of pathing).<br> Automata.png (attached) is an example of the tile mask (for those curious, cellular automata produce the mask).<br> I'd really appreciate any suggestions, or examples/links to algorithms with similar inputs. Thank you.<br>
  15. *Sigh* this thread again. Forgive me if I get a bit testy, but there's some obvious falsehoods that keep getting repeated. I don't mean to pick on you, Exodus, you're just the last person who repeated some of them. I may say "you" but I mean the people who keep making these arguments despite blatant evidence against them. [quote name='Exodus111' timestamp='1351731407' post='4996013'] The point here is trying to create game with open pvp, that would actually work. Full open PvP from the start, would mean that u would die immidietly.There would be someone next to u, as u started the game just killing new players as they entered. Before the game would load u would be dead.[/quote] Unfortunately this is just patently wrong, and it's not difficult for a full anyone/anywhere pvp game to remedy this. I mean no offense, but it really seems like you haven't investigated the actual mechanics behind the variety of games (past and present) that have had exactly such a system and have [i]not[/i] involved dying immediately. Eve Online, for instance, allows you to target someone the moment they enter space in their poor little noobship and instapop them with smarties (that is, kill a nooby the very first second they're in space in the super-high security zone), but this doesn't often happen. Why? Because the game makes it financially silly to do such a thing and, doing so is typically more profitable for the noob (who can respawn and loot your wreckage) than you. Good design mitigates griefing and does not require you to lose anyone/anywhere pvp. In a game with truly open pvp, permadeath and full loot, attacking a noob would be devastating if there were just a few guards around who attacked aggressors (ala Eve's Concord/sentries, or Darkfall's guards). The noob loses the time it took him to load up. The idiot griefer loses all the gear it took him to get to where he was. [quote]In this setting there is no character progression, or at the very best an unfair character progression, because those ppl who started the game in pre-launch would have a progression advantage over everyone else.[/quote]Not really. In general, it's not the beta or pre-launch players who lead in character progression, it's those with a lot of extra time on their hands (for instance, I was a GW2 pre-launch player and I [i]still[/i] have yet to hit level cap) or those who are more efficient if it's a grind based game. In games without progression, like almost every FPS out there, then players are naturally divided into categories by skill/experience. Neither set up is inherently "unfair." And ironically, it's the pre-launch players who write the guides for all the post-launch players to follow, and by doing so, drastically improve their efficiency. Pre-launchers are actually at a slight disadvantage, because they have to discover everything by trial and error without anyone to tell them "don't bother doing quest X, it takes 16 hrs and gives you 0.2 gold." [quote]The point is there has never been an MMO that FOCUSED on world pvp[/quote]Darkfall. Haven and Hearth. Eve. Dear god the dev blogs on Eve go on and on about how integral blowing each-other's faces off is to the economy. And the economy! It's like Adam Smith's wet dream. Stop making these statements, please. Please?